****Proof Sketch**. Our goal is to establish a minimax lower bound on the number of public and private samples needed for any \((\eps, \delta)\) private learner \(M\) that is \(\alpha\)-accurate in its estimation of the private mean, i.e., \(\|M(X) - \mu_{P}\|_2 \leq \alpha\), and for a fixed value of the shift parameter \(\tau > 0\). Following the typical approach of minimax lower bounds, we lower bound the minimax risk with the Bayes risk under a carefully chosen prior over the unknown parameters: \(\mu_P, v\), i.e., the private mean we want to estimate and the shift vector. The private mean \(\mu_P\) is sampled from a spherical Gaussian \(\mu_P \sim \cal{N}(0, \sigma^2 \mathbf{I}_d)\). Recall that \(\mu_Q = \mu_P + v\). We define the prior over \(v\) as \(v \sim \cal{N}(\mathbf{0}, \frac{\tau^2}{d} \cdot \mathbf{I}_d)\). Thus, in expectation over the sampling of \(v\), for any value of \(\mu_P\), \(\E{\|\mu_P-\mu_Q\|_2^2} = \tau^2\). The fact that there is a small probability of \(\|\mu_{P} - \mu_{Q}\|_2^2 \gg \tau^2\) will not impact our proof significantly.

Next, we define our test statistic \(Z_i\) for our fingerprinting method, matching the general form in 1 . In particular, when \(i \in [1,n]\), i.e., \(Z_i\) tries to measure the correlation between the mechanism output \(M(X)\) and a private sample \(X_i\), the statistic is given by: \[Z_i = \innerprod{X_i - \mu_P}{M(X) - \mu_P}\quad i \in \{1\ldots n\}.\] More interestingly, the statistic that measures the correlation with a public datapoint \(X_j\), where \(j \in \{n+1, \ldots, n+m\}\) is now re-weighted by a value that depends on the degree of shift \(\tau\), i.e., \[Z_j = \frac{1}{m\cdot\frac{\tau^2}{d}+1} \cdot \innerprod{X_j - \mu_P}{M(X) - \mu_P}\quad j \in \{n+1\ldots m+n\}\] Essentially, when we compute the sum \(\sum_i Z_i\), the weight on \(Z_i\) corresponding to a public datapoint is \(\Omega(1)\), when the shift is small: \(\tau = \gO(\sqrt{d/m})\), and up to constants matches the setting with no distribution shift \(\tau = 0\). On the other hand, as \(\tau \rightarrow \infty\), and the error from the shift dominates the sampling error over public data \(\tau = \omega(\sqrt{d/m})\), the weight on public \(Z_i\) is \(o(1)\). Intuitively, we expect any accurate mechanism \(M(X)\) to reduce its sensitivity over public data as the shift increases, and a similar effect is also captured by our test statistic. We upper bound the expected sum as \[\E\mathopen{}\mathclose{\left[\sum_i Z_i}\right] = \gO\paren{n\varepsilon\alpha + \tfrac{1}{1 + m \cdot \frac{\tau^2}{d}} \cdot \paren {\alpha \sqrt{md} + \alpha \tau \sqrt{m}}}\] using differential privacy arguments we outline in Section 2. Then, we lower bound the expected value of the sum \(\E[\sum_i Z_i]\) with \(\Omega(d)\) when \(\tau = \gO(\sqrt{d/m})\). For the lower bound, we use the Markov chain argument outlined in Section 2, and compute the posterior over \(\mu_P \mid X\) given all the data, where the posterior mean has lower order dependence on empirical mean of the public data, as the shift grows. Together, with the upper bound on \(\E [\sum_i{Z_i}]\), the \(\Omega(d)\) lower bound gives us the final result we need on the sample complexity of \(n\) and \(m\) for small values of \(\tau\). For large values of \(\tau\), the weight over public data points in our test statistic vanishes. In addition, we also need that \(m = \Omega(d/\alpha^2)\), for the public data to estimate its own mean \(\mu_Q\) to an accuracy of \(\alpha\). Combining this with the condition on \(\tau\), we establish that when \(\alpha \gsim \tau\), only then we expect the public data to be helpful, when the shift is large (\(\tau = \omega(\sqrt{d/m})\)). ◻

****Proof Sketch**. The proof follows the same high-level outline that we employ for mean estimation lower bounds. Specifically, we will again use the Bayesian view of the fingerprinting lemma, where we consider \(\beta\) sampled from some prior \(\cal{N}(0, \frac{1}{b}\cdot I_d)\) for some parameter \(b\), and analyze the posterior distribution of \(\beta\) conditioned on the public and private data. We also modify the test statistic using the score attack from [14], specifically defining \[Z_i = \langle \hat{\beta} - \beta, (y_i - x_i^\T \beta)x_i \rangle.\] The main technical ingredient in the proof is how we show that the test statistic is large when the estimated parameters \(\hat{\beta}\) are close to the true parameter \(\beta\), to obtain a lower bound on the error. We condition on a fixed, typical value of the features \(X\) and then compute the mean and covariance of the Gaussian posterior distribution \(\beta \mid X\), which is significantly more technical than in the case of mean estimation due to the presence of inverses of random matrices. ◻

Proof. We begin by providing an overview of the proof technique via fingerprinting statistics we define shortly.

Overview. \(\,\,\) First, we define the fingerprinting statistics, which are random variables, that depend on the randomness in the learner \(M\), the sampling of the dataset \(X\) and the unknown problem parameters \(\mu_\priv, v\). Informally, fingerprinting statistics are random variables which cannot take very high values without violating the privacy or the accuracy of the learner. Next, we show that under appropriate priors, the sum of these fingerprinting statistics cannot be too low without violating statistical lower bounds. Together, the privacy and statistical error bounds give us the final result in Theorem 8.

Fingerprinting statistics. \(\,\,\) We use \(\{Z_i\}_{i=1}^N\), one for each element in the dataset (includes both private and public samples), to denote the fingerprinting statistic. \[\begin{align} \label{eq:zi-definition} Z_i = \innerprod{M(X) - \mu_\priv}{X_i - \mu_\priv}, \quad \forall i \in [N] \end{align}\tag{4}\] Similarly, we define the dataset \(X^\prime_i\) that replaces the \(i^{th}\) element in \(X_\priv\) with a random sample from \(\mathcal{N}(\mathbf{0}, \mu_\priv)\) if \(i \in [n]\) and from \(\mathcal{N}(\mathbf{0}, \mu_\pub)\) otherwise: \[\begin{align} Z_i^\prime = \innerprod{M(X^\prime_i) - \mu_\priv}{X_i - \mu_\priv}, \quad \forall i \in [N] \end{align}\]

Next, we lower bound \(\sum_{i=1}^{n+m} Z_i = (n+m) \innerprod{M(X) - \mu_\priv}{\bar{\mu} - \mu_\priv}\), where \(\bar{\mu} = \frac{1}{n+m} \sum_{i=1}^{n+m} Z_i\), i.e., it is the empirical mean of the public and private samples combined. It is sufficient to lower bound \(\innerprod{M(X) - \mu_\priv}{\bar{\mu} - \mu_\priv}\).

We are now ready to prove the main result in Theorem 12. From Corollary 1 and Corollary 2, there exists constants \(c_1, c_2 > 0, n_0>0\), such that for all \(n \geq n_0, \delta \leq \frac{\varepsilon^2}{d}\), the following is true: \[\begin{align} c_1 d \; \leq \; \E \brck{\sum_{i=1}^{m+n} Z_i} \; \leq \; c_2\paren{n\varepsilon\alpha + \alpha \sqrt{md}}. \end{align}\] The above implies that either of the following conditions is true. First, \(n\varepsilon\alpha = \Omega(d)\) or \(n = \Omega(\frac{d}{\varepsilon\alpha})\). Second, \(\alpha\sqrt{md} = \Omega(d)\) or \(m = \Omega(\frac{d}{\alpha^2})\). Combining this result with Lemma 4, we conclude that either \(m = \Omega(\frac{d}{\alpha^2})\) or \(n + m = \Omega(\frac{d}{\alpha\varepsilon} + \frac{d}{\alpha^2})\). We can interpret this result as the following: either we need enough public samples to estimate the mean \(\mu_\priv\) to accuracy \(\alpha\) without the help of any private data, or we must have enough public and private data combined, to be able to treat the public data as private, and estimate the accuracy of \(\mu_\priv\) to accuracy \(\alpha\). ◻

Proof. The proof for the upper bound over \(\E[\sum_{i=1}^{n}Z_i]\) is similar to Proposition 10, which uses the DP constraint to show \(\E[\sum_{i=1}^{n}Z_i] = \gO(n \varepsilon\alpha)\). For the second term which sums the fingerprinting statistics corresponding to public samples, \(\E[\sum_{i=n+1}^{n+m}Z_i]\) we need to additionally account for the randomness in the direction of shift \(v\), when computing the expectation over the public mean \(\bar{\mu}_\pub\). Recall the definition of the fingerprinting statistics: \(Z_j = \inprod{M(X) - \mu_\priv}{x_j - \mu_\priv}\). Then, \[\begin{align} \E\mathopen{}\mathclose{\left[\sum_{j=n+1}^{n+m} Z_j}\right] &= \E\mathopen{}\mathclose{\left[\inprod{M(X) - \mu_\priv}{\sum_{j=n+1}^{n+m}(x_j - \mu_\priv)}}\right]\\ &\leq \sqrt{\E[\norm{M(X)-\mu_\priv}{2}^2]}\sqrt{\sum_{j=n+1}^{n+m}\E[ \norm{x_j - \mu_\priv}{2}^2]} \end{align}\] \[\begin{align} \E\mathopen{}\mathclose{\left[\sum_{j=n+1}^{n+m} Z_j}\right] & \leq \alpha \sqrt{\sum_{j=n+1}^{n+m}\E\brck{\E[\norm{x_j - \mu_\priv}{2}^2 \mid \mu_\priv]}}\\ &= \alpha \sqrt{\sum_{j=n+1}^{n+m}\E\brck{\E[\|x_j - \mu_\priv - v \mid \mu_\priv\|^2_2]} + \E[\|v\|_2^2]} = \gO(\alpha \sqrt{md} + \alpha\tau\sqrt{md}). \end{align}\] The first inequality uses Cauchy-Schwarz, and the second uses the bound on the accuracy of the mechanism \(M\). Finally, the last equality uses the tower law of expectations, followed by the indpendence between displacement \(v\) and private mean \(\mu_\priv\). Then, we simply apply the definitions for the priors over public and private means to get the final result. ◻

Proof. Follows immediately from Proposition 13 that upper bounds the second term in the summation and Proposition 10 which upper bounds the first term. ◻

Proof. Let \(\bar{\mu}_\pub\) be the empirical mean of the public data and \(\bar{\mu}_\priv\) be the empirical mean of the private data points. We can then derive the following joint distribution over \(\mu_\priv\), \(\bar{\mu}_\pub, \bar{\mu}_\priv\): \[\begin{align} & (\mu_\priv, \bar{\mu}_\pub, \bar{\mu}_\priv) \sim \mathcal{N}\mathopen{}\mathclose{\left(0, \Sigma}\right), \; \Sigma \in \mathbb{R}^{3d \times 3d} \;\;\;\;\; \text{and,} \label{eq:joint-distribution} \\ \Sigma &= \begin{pmatrix} \sigma^2 \mathbf{I}_d & \sigma^2 \mathbf{I}_d & \sigma^2 \mathbf{I}_d \\ \sigma^2 \mathbf{I}_d & (\sigma^2 + \frac{\tau^2}{d} + \frac{1}{m}) \cdot \mathbf{I}_d & \sigma^2 \mathbf{I}_d\\ \sigma^2 \mathbf{I}_d & \sigma^2 \mathbf{I}_d & (\sigma^2 + \frac{1}{n}) \cdot\mathbf{I}_d, \nonumber \end{pmatrix}. \end{align}\tag{8}\]

and \(\E[\mu_\priv \mid \bar{\mu}_\pub, \bar{\mu}_\priv]\) is given by \(\Sigma_{12}\Sigma_{22}^{-1}\paren{[\bar{\mu}_\pub, \bar{\mu}_\priv]^\top - [\E[\mu_\priv], \E[\mu_\priv]]^\top}\), where \(\Sigma_{12}\), and \(\Sigma_{22}\) are given by the top \(d \times 2d\), and bottom \(2d \times 2d\) submatrices of \(\Sigma\). Based, on this, we get: \[\begin{align} \Sigma_{12}\Sigma_{22}^{-1} = \mathopen{}\mathclose{\left( \frac{\sigma^2 / n}{(\sigma^2 + \tau^2/d + 1/m)(\sigma^2 + 1/n) - \sigma^4} I_d, \frac{\sigma^2(\tau^2/d + 1/m)}{(\sigma^2 + \tau^2/d + 1/m)(\sigma^2 + 1/n) - \sigma^4} I_d}\right) \end{align}\] Then, the mean of the posterior distribution over \(\mu_\priv\) is given by: \[\begin{align} \E[\mu_\priv \mid \bar{\mu}_\pub, \bar{\mu}_\priv] &= \mathopen{}\mathclose{\left( \frac{\sigma^2 / n}{(\sigma^2 + \tau^2/d + 1/m)(\sigma^2 + 1/n) - \sigma^4} I_d}\right)\cdot(\bar{\mu}_{\pub} - \E[\mu_{\pub}]) \\ & \quad\quad +\mathopen{}\mathclose{\left(\frac{\sigma^2(\tau^2/d + 1/m)}{(\sigma^2 + \tau^2/d + 1/m)(\sigma^2 + 1/n) - \sigma^4} I_d}\right) \cdot(\bar{\mu}_{\priv} - \E[\mu_{\priv}]) \\ &= \frac{\frac{\sigma^2}{n} \cdot \bar{\mu}_\pub + \sigma^2 \bar{\mu}_\priv \cdot (\tau^2/d + \frac{1}{m})}{\sigma^2 (\tau^2/d + \frac{1}{m} + \frac{1}{n}) + \frac{\tau^2}{nd} + \frac{1}{mn}} \end{align}\] From the expression above it it easy to derive \(w_\pub\) and \(w_\priv\) in the statement of Lemma 5. ◻

Proof. Directly applying Lemma 5 we get: \[\begin{align} &\E\brck{\mu_\priv \mid X} - \bar{X} \nonumber \\ ={} &\frac{\frac{\sigma^2}{n} \cdot \bar{X}_\pub + \sigma^2 \bar{X}_\priv \cdot (\tau^2/d + \frac{1}{m})}{\sigma^2 (\tau^2/d + \frac{1}{m} + \frac{1}{n}) + \frac{\tau^2}{nd} + \frac{1}{mn}} - \frac{n}{\frac{m}{(m\tau^2/d+1)}+n}\cdot\bar{X}_\priv - \frac{\frac{m}{(m\tau^2/d+1)}}{\frac{m}{(m\tau^2/d+1)}+n}\cdot \bar{X}_\pub\tag{9} \\ ={} &\bar{X}_\pub \paren{ \frac{\frac{\sigma^2}{n}}{\sigma^2 (\tau^2/d + \frac{1}{m} + \frac{1}{n}) + \frac{\tau^2}{nd} + \frac{1}{mn}} - \frac{\frac{m}{(m\tau^2/d+1)}}{\frac{m}{(m\tau^2/d+1)}+n}} \nonumber \\ &+ \bar{X}_\priv \paren{ \frac{\sigma^2(\tau^2/d + 1/m)}{\sigma^2 (\tau^2/d + \frac{1}{m} + \frac{1}{n}) + \frac{\tau^2}{nd} + \frac{1}{mn}}- \frac{n}{\frac{m}{(m\tau^2/d+1)}+n}}. \tag{10} \end{align}\]

To bound the expected squared norm of the above term, we first need to bound terms \(\alpha, \beta\) defined as follows: \[\alpha \eqdef \frac{\frac{\sigma^2}{n}}{\sigma^2 (\tau^2/d + \frac{1}{m} + \frac{1}{n}) + \frac{\tau^2}{nd} + \frac{1}{mn}} - \frac{\frac{m}{(m\tau^2/d+1)}}{\frac{m}{(m\tau^2/d+1)}+n}\] \[\beta \eqdef \frac{\sigma^2(\tau^2/d + 1/m)}{\sigma^2 (\tau^2/d + \frac{1}{m} + \frac{1}{n}) + \frac{\tau^2}{nd} + \frac{1}{mn}} - \frac{n}{\frac{m}{(m\tau^2/d+1)}+n}\]

Let \(\sigma^2 = 1\) and define \(\kappa := 1 + \frac{m \tau^2}{d}\). Then we can simplify in the following way:

\[\begin{align} \alpha = \frac{-m\kappa}{(n \kappa + \kappa +m)(n\kappa+m)}, \quad \beta = \frac{-n\kappa^2}{(n \kappa + \kappa +m)(n\kappa+m)} \end{align}\]

Thus, \(\alpha \bar{X}_\pub + \beta \bar{X}_\priv\) can be written as: \[\begin{align} \alpha \bar{X}_\pub + \beta \bar{X}_\priv = -\frac{\paren{\kappa^2 \sum_{i=1}^n X_i + \kappa \sum_{j=n+m}^{n+1} X_j}}{(m+n\kappa+\kappa)(m+n\kappa)} \label{eq:1001} \end{align}\tag{11}\]

We can bound the \(\norm{\cdot}{2}^2\) for the expression, by noting that \(\norm{\sum_{i=1}^n X_i }{2}^2 = \gO(nd)\) and \(\norm{\sum_{i=m+1}^{n+m} X_i }{2}^2 = \gO(md)\). Applying this in the above expression, and dividing both numerator and denominator by \(\kappa^2\) we get the final result: \[\begin{align} \norm{\E\brck{\mu_\priv \mid X} - \bar{X} \nonumber}{2}^2 &= \gO\paren{\frac{d(n+\frac{m}{\kappa})}{ \paren{\frac{m}{\kappa}+n+1}^2\paren{\frac{m}{\kappa}+n}^2}} \\ &= \gO\paren{\frac{d}{\paren{n+\frac{m}{\kappa}}^3}} \end{align}\] This completes the proof of Lemma 6. ◻

Proof. Similar to our previous proofs on the lower bound for the expected sum of test statistics, we manipulate the following sum into two terms. \[\begin{align} &\E_{\mu_\priv, X, v}\mathopen{}\mathclose{\left[\sum_{i=1}^{n} Z_i + \frac{1}{\frac{m}{d}\cdot\tau^2 + 1} \cdot \sum_{i=n+1}^{n+m} Z_i }\right] \nonumber \\ &= (n+\frac{m}{(m\tau^2/d+1)}) \cdot \mathopen{}\mathclose{\left(\E\mathopen{}\mathclose{\left[\|\bar{X}-\mu_\priv\|_2^2}\right] + \E \mathopen{}\mathclose{\left\langle M(X)-\bar{X}, \bar{X}-\mu_\priv}\right\rangle }\right), \label{eq:breakdown} \end{align}\tag{12}\]

Given, \(X\), the random variable \(M(X)\) is independent of \(\mu_\priv\). \[\begin{align} \label{eq:breakdown-2} \E_{\mu_\priv, X, v} & \brck{ \mathopen{}\mathclose{\left\langle M(X)-\bar{X}, \bar{X}-\mu_\priv}\right\rangle } \;\; =\;\; \E_X \brck{\innerprod{\E_{\mu_\priv, v \mid X}[M(X)-\bar{X}]}{\E_{\mu_\priv, v \mid X}[\bar{X} - \mu_\priv]}} \nonumber\\ & \;\; \leq \;\; \sqrt{\E_X\|\E_{\mu_\priv, v \mid X}[M(X)-\bar{X}]\|_2^2} \cdot \sqrt{\E_X\|\E_{\mu_\priv, v \mid X}[\bar{X} - \mu_\priv]\|_2^2}, \end{align}\tag{13}\] where the inequality uses Cauchy-Schwarz. We can further use the convexity of \(\|\cdot\|_2^2\) in the first term above to arrive at the following upper bound. \[\begin{align} \label{eq:breakdown-4} & \E_{\mu_\priv, X, v} \brck{ \mathopen{}\mathclose{\left\langle M(X)-\bar{X}, \bar{X}-\mu_\priv}\right\rangle} \nonumber\\ & \;\; \leq \;\; \sqrt{\E_{\mu_\priv, v , X} \|[M(X)-\bar{X}]\|_2^2} \cdot \sqrt{\E_X\|\E_{\mu_\priv, v \mid X}[\mu_\priv] - \bar{X}\|_2^2}, \end{align}\tag{14}\] Next, we proceed by bounding \(\E_{\mu_\priv, v , X} \|[M(X)-\bar{X}]\|_2^2\). \[\begin{align} \E_{\mu_\priv, v , X} \|[M(X)-\bar{X}]\|_2^2 &= \E_{\mu_\priv, v , X} \|\mu_\priv-\bar{X}]\|_2^2 + \E_{\mu_\priv, v , X} \|[M(X)-\mu_\priv]\|_2^2 \nonumber \\ & \leq \E_{\mu_\priv, v , X} \|\mu_\priv-\bar{X}\|_2^2 + \alpha^2 \label{eq:breakdown-8-2} \end{align}\tag{15}\] Recall the definition of \(\bar{X}\): \[\begin{align} \bar{X} \eqdef \bar{X}_\pub \cdot \frac{\frac{m}{(m\tau^2/d +1)}}{n+\frac{m}{(m\tau^2/d +1)}} + \bar{X}_\priv \cdot \frac{n}{n+\frac{m}{(m\tau^2/d +1)}}, \end{align}\] with \(\bar{X}_\pub\) and \(\bar{X}_\priv\) being the empirical mean over public and private data points. Plugging this into , we get: \[\begin{align} \E_{\mu_\priv, v , X} \|[M(X)-\bar{X}]\|_2^2 & \leq \alpha^2 + \frac{ \frac{md}{\kappa^2}}{(n+m/\kappa)^2} + \frac{nd}{(n+m/\kappa)^2} \nonumber \\ & \leq \alpha^2 + \frac{ \frac{md}{\kappa^2}}{(n+m/\kappa)^2} + \frac{nd}{(n+m/\kappa)^2} \nonumber \\ & = \gO\paren{\alpha^2 + \frac{d}{(n+m/\kappa)}} \label{eq:breakdown-11}, \end{align}\tag{16}\] where the second inequality follows from \(\kappa \geq 1\). Finally, we do the following plugins: we plug in,

1. the result from Lemma 6 for the bound on \(\E_X\|\E[\mu_\priv \mid X] - \bar{X}\|^2_2\) into 14 ,

2. the result on the bound on \(\Ex{\|M(X) - \bar{X}\|_2^2}\) in 16 into 14 ,

3. the bound on \(\Ex{\|\bar{X}-\mu_\priv\|^2_2}\) derived as part of 16 into 12

Together, these complete the proof of the lower bound stated in Lemma 7.

Finally, we are ready to put together the upper and lower bounds on \(\E[\sum_i Z_i]\) to arrive at the final result in Theorem 12. From Corollary 3 and Lemma 7 we conclude that whenever \(\tau = \gO(\sqrt{d/m})\), there exists positive constants \(c_1, c_2\) and values \(n_0, m_0\), such that for \(n \geq n_0, m\geq m_0\): \[\begin{align} c_2 \cdot d \; \leq \; \sum_{i=1}^{n} \E[Z_i] + \frac{1}{\kappa} \cdot \sum_{i=n+1}^{n+m} \E[Z_i] & \; \leq \;c_1\paren{n\varepsilon\alpha + {{\alpha\sqrt{md}}{}}} \end{align}\] This means that when either \(n = \Omega(\frac{d}{\varepsilon\alpha})\) or \(m = \Omega(\frac{d^2}{\alpha})\). Note that the lower bound in Lemma 4 is still applicable for \(n\). Together, this tells us that when \(\tau = \gO(\sqrt{d/m})\), then either \(n = \Omega(\frac{d}{\varepsilon\alpha} + \frac{d}{\alpha^2})\) or \(m = \Omega(\frac{d}{\alpha^2})\). This completes the first result in Theorem 12. For the second part, let us consider the case where \(\tau = \omega(\sqrt{d/m})\). Then, either there exists constants \(c_1, c_2\), such that for all \(n\geq n_0\): \[c_1 d \leq c_2 n\varepsilon \alpha,\] in which case \(n = \Omega(\frac{d}{\varepsilon\alpha})\) or there exists constants \(c_1, c_2\) and values \(n_0, m_0\), such that for all \(n \geq n_0, m \geq m_0\) the following holds: \[d \; \leq \; \frac{\alpha\tau\sqrt{md}+ \alpha \sqrt{md}}{1+m \tau^2/d},\] which implies: \[c_1 d \leq \alpha \tau \frac{\sqrt{md}}{m \tau^2/d}.\] The above holds when \(\alpha \gsim \tau\). This completes all conditions in the proof of Theorem 12. ◻

Proof. We have \[\begin{align} z(1 - \sqrt{d/z} - \psi)^2 &= z(9/10 - \sqrt{d/z})^2\\ &= z(81/100 - (18/10)\sqrt{d/z} + d/z)\\ &= z(81/100) - (18/10)\sqrt{dz} + d\\ &\geq z(81/100) - (18/10)\sqrt{z^2/100} + d\\ &\geq z(81 - 18)/100 = 63/100 \cdot z. \end{align}\] ◻

Proof. We have \[\begin{align} z(1 + \sqrt{d/z} + \psi)^2 &= z(9/10 + \sqrt{d/z})^2\\ &= z(81/100 + (18/10)\sqrt{d/z} + d/z)\\ &= z(81/100) + (18/10)\sqrt{dz} + d\\ &\leq z(81/100) + (18/10)\sqrt{z^2/100} + z/100\\ &\leq z(81 - 18 + 1)/100 = 64/100 \cdot z. \end{align}\] ◻

Proof. When conditioned on \(\beta\), \((y_i - x_i^\T\beta)x_i\) is independent of \(M(\data_i^\prime) - \beta\), and \(\E[(y_i - x_i^\T\beta)x_i \mid \beta] = 0\) (because \(\E[\eta_i x_i] = 0\)). Thus, we have \(\E[Z_i^\prime] = \E[\E[Z_i^\prime \mid \beta]] = 0\).

Next, we bound \(\E[(Z_i^\prime)^2 | \beta]\) and similarly use the law of total expectation to get the upper bound on \(\E[(Z_i^\prime)^2]\). Note that we have \(y_i = x_i^\T \beta + \eta_i\), thus \[\begin{align} \E[(Z_i^\prime)^2 | \beta] &= \E\brck{\sum_{j,k} (M(\data_i^\prime) - \beta)_j (M(\data_i^\prime) - \beta)_k (\eta_i x_i)_j (\eta_i x_i)_k \vert \beta} \\ &= \sum_j \E\brck{( M(\data_i^\prime) - \beta)_j^2 (\eta_i x_i)_j^2 \vert \beta}\\ &= \sum_j \E\brck{( M(\data_i^\prime) - \beta)_j^2 \vert \beta} \Ex{(\eta_i x_i)_j^2 \vert \beta}\\ &= \Ex{\normtwo{M(\data_i^\prime) - \beta)_j^2}^2 \vert \beta} \leq \alpha^2. \end{align}\]

The second equality uses the fact the coordinates of \(\eta\) and \(x_i\) are sampled independently, and the third equality uses that \(M(\data_i') - \beta\) is conditionally independent of \(\eta_i x_i\) given \(\beta\) (because \(x_i\) and \(y_i\) are resampled in \(\data_i'\)). The final step uses the accuracy of the mechanism \(M\) and the variance of \(\eta_i\) and \(x_i\). ◻

Proof. Since \(\data\) and \(\data_i^\prime\) differ by a single element, and \(M\) is \((\eps, \delta)\) differentially private, we can use the fact that the outputs \(M(\data)\) and \(M(\data_i^\prime)\) (and therefore, by the postprocessing property of DP, \(Z_i\) and \(Z_i'\)) cannot be too different. In particular, we invoke Proposition 1. \[\mathopen{}\mathclose{\left| \mathbb{E}[Z_i] - \mathbb{E}[Z'_i] }\right| \leq 2\eps \cdot \mathbb{E}[|Z'_i|] + 2\sqrt{\delta} \cdot \mathbb{E}[Z_i^2 + (Z'_i)^2] \leq 2(\eps + \sqrt{\delta}) \cdot \sqrt{\mathbb{E}[(Z'_i)^2]} + 2\sqrt{\delta \cdot \mathbb{E}[Z_i^2]}.\] Next, we apply Proposition 15. \[\mathbb{E}[Z_i] \leq O((\varepsilon+ \sqrt{\delta})\alpha) + 2\sqrt{\delta \cdot \mathbb{E}[Z_i^2]}.\] Next, we bound \(\E [Z_i^2]\) with Cauchy-Schwarz followed by the accuracy of \(M\), and the concentration of \(\eta_i x_i\): \[\begin{align} \E [Z_i^2] \;\; &\leq \;\; \sqrt{\E[\|M(\data) - \mu_\priv\|_2^4]} \sqrt{\E[\|\eta_i x_i\|_2^4]} \\ &= \;\; O(\alpha^2 d) \end{align}\] Plugging this result into the equation above, we conclude \(\E[Z_i]=O(\varepsilon\alpha + \sqrt{\delta d}\alpha)\). Recall from the conditions in Theorem 6, \(\delta \leq \frac{\varepsilon^2}{d}\). Thus, \(\E[Z_i] = O(\varepsilon\alpha)\). ◻

Proof. Recall the definition of the fingerprinting statistics: \(\E[Z_j] = \E\mathopen{}\mathclose{\left[\inprod{M(x) - \beta}{(y_i - x_i^\T \beta)x_i}}\right]\). Then, \[\begin{align} \E\mathopen{}\mathclose{\left[\sum_{i=n}^{n+m} Z_i}\right] &= \E\mathopen{}\mathclose{\left[\inprod{M(\data) - \beta_\priv}{\sum_{i=n}^{n+m}(y_i - x_i^\T \beta)x_i}}\right]\\ &\leq \sqrt{\E[\norm{M(\data)-\beta}{2}^2]}\sqrt{\sum_{i=n}^{n+m}\E[ \norm{\eta_ix_i}{2}^2]} \\ &= \gO(\alpha \sqrt{md}). \end{align}\] The first inequality uses Cauchy-Schwarz, and the second uses the bound on the accuracy of the mechanism \(M\) and the variance of \(\eta_ix_i\). ◻

Proof. Rewrite \(\hat{\beta} = (X^\T X)^{-1}X^\T y = (X^\T X)^{-1}X^\T (X\beta + \eta) = \beta + (X^\T X)^{-1}X^\T \eta\).

Then \(\hat{\beta} - \beta = (X^\T X)^{-1}X^\T \eta\). Hence, \(X(\hat{\beta} - \beta) = X(X^\T X)^{-1}X^\T \eta\).

Finally \[\require{physics} \begin{align} \Ex{\normtwo{X(X^\T X)^{-1}X^\T \eta}^2} &= \Ex{\Tr(\eta^T X(X^\T X)^{-1}X^\T \eta)}\\ &= \sigma^2 d \end{align}\] ◻

Proof. First, note that we can rewrite \(\Ex{\normtwo{\Lambda^{-1}}^4}\) as follows: \[\begin{align} \Ex{\normtwo{\Lambda^{-1}}^4} &= \Ex{\normtwo{(aX^\T X + bI)^{-1}}^4}\\ &= \Ex{\frac{1}{(a\sigma_{\min}(X^\T X) + b)^4}} \end{align}\]

We will split the expectation into two conditional expectations: \[\begin{align} \Ex{\normtwo{\Lambda^{-1}}^4} = \condEx{\normtwo{\Lambda^{-1}}^4}{\sigma_{\min}(X^\T X) \in (0, t]}\Pr[\sigma_{\min}(X^\T X) \in (0, t)] + \\ \condEx{\normtwo{\Lambda^{-1}}^4}{\sigma_{\min}(X^\T X) \in [t, \infty)]}\Pr[\sigma_{\min}(X^\T X) \in [t, \infty)]. \end{align}\] for some \(0 < t < 1\).

For any \(\sigma \geq 0\) we can bound \(\Ex{\normtwo{\Lambda^{-1}}^4} < 1/b^4\), and when \(\sigma \geq t\) we additionally have \(\Ex{\normtwo{\Lambda^{-1}}^4} \leq 1/(at + b)^4\). Then the above simplifies to \[\begin{align} &\condEx{\normtwo{\Lambda^{-1}}^4}{\sigma_{\min}(X^\T X) \in (0, t]}\Pr[\sigma_{\min}(X^\T X) < t] + \\ &\condEx{\normtwo{\Lambda^{-1}}^4}{\sigma_{\min}(X^\T X) \in [t, \infty)]}\Pr[\sigma_{\min}(X^\T X) \in [t, \infty)]\\ &= \frac{1}{b^4}\Pr[\sigma_{\min}(X^\T X) < t] + \frac{1}{(at+b)^4}\Pr[\sigma_{\min}(X^\T X) \geq t] \end{align}\] We approximate \(\Pr[\sigma_{\min}(X^\T X) \geq t] \leq 1\), giving \[\begin{align} &= \frac{1}{b^4}\Pr[\sigma_{\min}(X^\T X) < t] + \frac{1}{(at+b)^4} \end{align}\]

It then remains to bound \(\Pr[\sigma_{\min}(X^\T X) < t]\).

As \(X^\T X\) is symmetric and PSD, we have \(\sigma_{\min}(X^\T X) = \lambda_{\min}(X^\T X) = \sigma_{\min}(X)^2\).

Now we have \[\begin{align} \Pr[\sigma_{\min}(X^\T X) \in (0, t]] &\leq \Pr(\sigma_{\min}(X^\T X) < t)\\ &= \Pr(\sigma_{\min}(X)^2 < t) \end{align}\]

We can now use Lemma 8. Setting \(t = N(1-\sqrt{d/N} - \psi)^2\) for some \(0 < \psi < 1 - \sqrt{d/N}\), \(\Pr(\sigma_{\min}(X)^2 < t) \leq e^{-N\psi^2/2}\).

Using Fact 14, we can upper bound this by, e.g., \(O(1/N^8)\).

Thus, we have \(\frac{1}{b^4}\Pr[\sigma_{\min}(X^\T X) < t] = O(\frac{1}{b^4N^8})\), so in total we have \[\begin{align} \Ex{\normtwo{\Lambda^{-1}}^4} &\leq \frac{1}{b^4}\Pr[\sigma_{\min}(X^\T X) < t] + \frac{1}{(at+b)^4}\\ &\leq O\mathopen{}\mathclose{\left(\frac{1}{b^4N^8}}\right) + O\mathopen{}\mathclose{\left(\frac{1}{(at+b)^4}}\right) \end{align}\]

Assuming \(N > 100d\), we have the constraint \(0 < \psi < 9/10\). We set \(\psi = 1/10\). Then this gives \[\begin{align} t &= N(1-\sqrt{d/N} - 1/10)^2 \\ &= N(9/10)^2 - 2(9/10)\sqrt{dN} + d \end{align}\]

Since we assume \(N > 100d\) (i.e. \(d < N/100\)), \[\begin{align} &\geq N(81/100) - (18/10)\sqrt{N^2/100} + d\\ &= N(81-18)/100 + d = \Omega(N).\label{eq:eigval-const} \end{align}\tag{17}\]

Thus, for \(b > 1/N\), we have \[\begin{align} O\mathopen{}\mathclose{\left(\frac{1}{b^4N^8}}\right) + O\mathopen{}\mathclose{\left(\frac{1}{(at+b)^4}}\right) \leq O\mathopen{}\mathclose{\left(\frac{1}{b^4N^8}}\right) + O\mathopen{}\mathclose{\left(\frac{1}{(aN+b)^4}}\right) \leq O\mathopen{}\mathclose{\left(\frac{1}{(aN+b)^4}}\right). \end{align}\] ◻

Proof. Let \(N = m+n\) be the total number of datapoints (including both public and private). First, we simplify \(X^T y = X^T(X\beta + \Vec{\eta})\). Then, we use the identity \((a+b)^2 \leq 2(a^2 +b^2)\) twice and get: \[\begin{align} \label{eq:100} \Ex{\|X^T y\|_2^4} \leq \Ex{\|X^TX \beta\|_2^4} + \Ex{\|X^T\Vec{\eta}\|_2^4}. \end{align}\tag{18}\] Now, we bound each of the above two terms separately. First, we start with the second term \(\Ex{\|X^T\eta\|_2^4}\). \[\begin{align} \Ex{\|X^T\Vec{\eta}\|_2^4} &= \Ex{\normtwo{\sum\nolimits_{i\in [N]} x_i \eta_i}^4} \\ &= \Ex{{\sum\nolimits_{i,j,k,l\in [N]} x_i^T x_j x_k^T x_l \cdot \eta_i \eta_j \eta_k \eta_l}} \end{align}\] Since \(\eta_i \perp \eta_j\) whenever \(i \neq j\) and \(\Ex{\eta} = 0\), it is easy to see that the only non-zero terms in the expectation above are when: (i) \(i=j=k=l\); (ii) \(i=j, k=l, i \neq k\); (iii) \((i,j)=(k,l), i \neq j\). Thus, the summation breaks down into: \[\begin{align} \label{eq:101} \Ex{\|X^T\Vec{\eta}\|_2^4} &= N \Ex{\normtwo{x}^4} \Ex{\eta^4} + N (N-1) \paren{\Ex{\normtwo{x}^2} \Ex{\eta^2}}^2 \nonumber \\ & \quad + N (N-1) \Ex{\normtwo{x}^2} \paren{\Ex{\eta^2}}^2 \\ &= 3N\Ex{\normtwo{x}^4} + N(N-1) \paren{\Ex{\normtwo{x}^2}}^2 + \Ex{\normtwo{x}^2} \nonumber \\ &= \gO(N^2 d^2). \nonumber \end{align}\tag{19}\] In the above equations, the first equality uses \(x_i \perp x_j\) when \(i \neq j\), and \(x_i \perp \eta_i, \forall i\). The second uses the fact that \(\Ex{\eta^4} = 3\) and \(\Ex{\eta^2} = 1\). Finally, the last equality uses \(\Ex{\normtwo{x}^2} = d\) and \(\Ex{\normtwo{x}^4} = \gO(d^2)\).

Next, we look at the first term in 18 . Using the independence of \(X\) and \(\beta\), we bound this as follows: \[\begin{align} \Ex{\normtwo{X^\T X\beta}^4} &\leq \Ex{\normtwo{X^\T X}^4 \normtwo{\beta}^4}\\ &= \Ex{\normtwo{X^\T X}^4}\Ex{\normtwo{\beta}^4} \end{align}\]

Now we have \(\Ex{\normtwo{\beta}^4} = O(\frac{d^2}{b^2})\). Further, we can bound \(\Ex{\normtwo{X^\T X}^4} = O(N^4)\).

This gives an overall bound of \(\Ex{\normtwo{X^\T X\beta}^4} = O(N^4d^2/b^2)\). Combining with the previous term gives the result. ◻

Proof. From Lemma 13 and Lemma 14, we derive the following: \[\begin{align} & \sqrt{\mathbb{E}_{X,\eta} \mathbb{E}_{\hat{\beta}} \mathopen{}\mathclose{\left\| M(X,y) - \hat{\beta} }\right\|_2^2 \cdot \sqrt{b^4\Ex{\normtwo{\Lambda^{-1}}^4}\Ex{\normtwo{X^\T y}^4}}}\\ & \leq \sqrt{\mathbb{E}_{X,\eta} \mathbb{E}_{\hat{\beta}} \mathopen{}\mathclose{\left\| M(X,y) - \hat{\beta} }\right\|_2^2 \cdot b^2 (\frac{1}{(aN+b)^2}) \cdot \sqrt{N^4d^2/b^2 + N^2d^2} } \nonumber \\ &\leq \sqrt{\mathopen{}\mathclose{\left(\sigma^2d/N + \alpha^2 }\right) b^2 (\frac{1}{(aN+b)^2}) \cdot (\sqrt{N^4d^2/b^2} + \sqrt{N^2d^2})}\\ &\leq \sqrt{\mathopen{}\mathclose{\left(\sigma^2d/N + \alpha^2 }\right) b^2 (\frac{1}{(aN)^2}) \cdot (N^2d/b + Nd)} \\ &\leq \sqrt{\mathopen{}\mathclose{\left(\sigma^2d/N + \alpha^2 }\right) b \cdot \mathopen{}\mathclose{\left(\frac{d}{a^2} + \frac{db}{a^2 N}}\right)} \end{align}\] Note that generally we will set \(a = \sigma^2\). Let \(b = 1/d\). Also, note \(\alpha = O(1)\). Then: \[\begin{align} &\leq \sqrt{\mathopen{}\mathclose{\left(\sigma^2d/N + \alpha^2 }\right) (1/d) \cdot (\sigma^2d + \sigma^4/N)}\\ &\leq \sqrt{\mathopen{}\mathclose{\left(\sigma^2d/N + \alpha^2 }\right) \cdot (\sigma^4 + \sigma^4/(Nd))}\\ &= O(1), \end{align}\] since \(\alpha^2 = \gO(1)\). ◻

Proof. Let \(\Sigma^{-1}_{\pub} = (\Sigma^{-1})_{11} = (\frac{\tau^2}{d}X_\pub X_\pub^\T + \sigma^2 I_m)^{-1}\). Then we have \[\begin{align} \Ex{\sum_{i=n}^{n+m} Z_i} &= \Ex{\inprod{M(X, y) - \beta}{X_{\pub}^\T \Sigma^{-1}_{\pub}(X_\pub\beta - y_\pub)}}\\ &= \Ex{\inprod{M(X, y) - \beta}{X_{\pub}^\T \Sigma^{-1}_{\pub}(X_\pub\beta - (X_\pub\beta + X_\pub v + \eta_\pub)}}\\ &\leq \sqrt{\Ex{\normtwo{M(X, y) - \beta}^2}}\sqrt{\Ex{\normtwo{X_\pub^\T\Sigma^{-1}_\pub(X_\pub v + \eta_\pub)}^2}} \end{align}\]

We first bound just the second term. \[\require{physics} \begin{align} &\Ex{\normtwo{X_\pub^\T\Sigma^{-1}_\pub(X_\pub v + \eta_\pub)}^2} \\ &= \Ex{\Tr\mathopen{}\mathclose{\left((X_\pub v + \eta_\pub)^\T \Sigma^{-1}_\pub X_\pub X_\pub^\T\Sigma^{-1}_\pub(X_\pub v + \eta_\pub)}\right)}\\ &= \Ex{\Tr\mathopen{}\mathclose{\left(\Sigma^{-1}_\pub X_\pub X_\pub^\T\Sigma^{-1}_\pub(X_\pub v + \eta_\pub)(X_\pub v + \eta_\pub)^\T }\right)}\\ &= \Tr(\varEx{X}{\Ex{\Sigma^{-1}_\pub X_\pub X_\pub^\T\Sigma^{-1}_\pub \vert X}\Ex{(X_\pub v + \eta_\pub)(X_\pub v + \eta_\pub)^\T\vert X}})\\ &= \Tr(\varEx{X}{\Sigma^{-1}_\pub X_\pub X_\pub^\T\Sigma^{-1}_\pub\Sigma_\pub})\\ &= \varEx{X}{\Tr(X_\pub^\T\Sigma^{-1}_\pub X_\pub)} \end{align}\]

Applying the Woodbury identity to \(\Sigma^{-1}_\pub\), we get \[\require{physics} \begin{align} &= \varEx{X}{\Tr(X_\pub^\T (\frac{1}{\sigma^2}I_m - \frac{1}{\sigma^4}X_\pub^\T(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T)X)}\\ &= \varEx{X}{\Tr(X_\pub^\T\frac{1}{\sigma^2}X)} - \varEx{X}{\Tr(X_\pub^\T(\frac{1}{\sigma^4}X_\pub(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T)X)} \end{align}\]

The first term is \(\frac{1}{\sigma^2}md\) by standard Frobenius norm bounds. Then we need to lower bound the second term: \[\require{physics} \begin{align} &\varEx{X}{\Tr(\frac{1}{\sigma^4}(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub X_\pub^\T X)}\\ &\geq \varEx{X}{\frac{1}{\sigma^4}\normtwo{(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub X_\pub^\T X}}\\ &\geq \frac{1}{\sigma^4}\varEx{X}{\lambda_{\min}(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}\Tr(X_\pub^\T X_\pub X_\pub^\T X_\pub)}\\ &= \frac{1}{\sigma^4}\varEx{X}{\frac{1}{\normtwo{(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)}}\normf{X_\pub^\T X_\pub}^2}\\ &\geq \frac{1}{\sigma^4}\varEx{X}{\frac{1}{\normtwo{(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)}}\mathopen{}\mathclose{\left(\sum_{j=1}^d \lambda_j(X_\pub^\T X_\pub)^2}\right)}\\ &\geq \frac{1}{\sigma^4}\varEx{X}{\frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\lambda_{\max}(X_\pub^\T X_\pub)}\mathopen{}\mathclose{\left(d\lambda_{\min}(X_\pub^\T X_\pub)^2}\right)} \end{align}\]

We can break the above conditional expectation into two components, one where \(\lambda_{\min}(X_\pub^\top X_\pub) \in (0, t_1], \lambda_{\max}(X_\pub^\top X_\pub) \in [t_2, \infty), t_1 \leq t_2\), and the other given by its complement, for some appropriately chosen \(t_1, t_2> 0\).

\[\begin{align} &\frac{1}{\sigma^4}\varEx{X}{\frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\lambda_{\max}(X_\pub^\T X_\pub)}\mathopen{}\mathclose{\left(d\lambda_{\min}(X_\pub^\T X_\pub)^2}\right)} \\ &\geq \frac{1}{\sigma^4} \cdot \frac{dt_1^2}{\frac{d}{\tau^2} + \frac{t_2}{\sigma^2}} \Pr\paren{\lambda_{\min}(X_\pub^\top X_\pub) \geq t_1} \cdot \Pr\paren{\lambda_{\max}(X_\pub^\top X_\pub) \leq t_2} \end{align}\]

The two tail bounds on the eigen values of \(X_\pub^\top X_\pub\) that appear in the above equation can be resolved using Lemma 8, and Lemma 9. When \(N \geq 100d\), then with constant probability \(\lambda_{\min} (X_\pub^\top X_\pub) = m - \Omega(1)\) and \(\lambda_{\max} (X_\pub^\top X_\pub) = m + \gO(1).\) Plugging this result into the above lower bound, we conclude: \[\begin{align} \frac{1}{\sigma^4}\varEx{X}{\frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\lambda_{\max}(X_\pub^\T X_\pub)}\mathopen{}\mathclose{\left(d\lambda_{\min}(X_{\pub}^\T X_{\pub})^2}\right)} \geq \frac{1}{\sigma^4}\Omega\mathopen{}\mathclose{\left(\frac{dm^2}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m}}\right) \end{align}\]

Thus, in total, we have: \[\begin{align} \Ex{\normtwo{X_\pub^\T\Sigma^{-1}_\pub(X_\pub v + \eta_\pub)}^2} \leq \frac{1}{\sigma^2}md - \frac{1}{\sigma^4}\mathopen{}\mathclose{\left(\frac{m^2d}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m} }\right). \end{align}\]

Finally, from the accuracy assumption of the mechanism \(M\) we have \(\sqrt{\Ex{\normtwo{M(X, y) - \beta}^2}} \leq \alpha\). Putting it all together, we arrive at the inequality: \[\begin{align} \Ex{\sum_{i=n}^{n+m} Z_i} = \gO \paren{ \alpha\sqrt{\frac{1}{\sigma^2}md - \frac{1}{\sigma^4}\mathopen{}\mathclose{\left(\frac{m^2d}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m} }\right)}}. \end{align}\]

The statement of Lemma 16 follows from applying the non-shifted upper bound over private samples in Proposition  16 along with the above result. ◻

Proof. First, we simplify \(\hat{\beta} - \beta\): \[\begin{align} \hat{\beta} - \beta &= (X^\T \Sigma^{-1}X)^{-1}X^\T \Sigma^{-1}(X\beta + Pv + \eta) - \beta\\ &= (X^\T \Sigma^{-1}X)^{-1}X^\T \Sigma^{-1}(Pv + \eta) \end{align}\]

Then we have, \[\require{physics} \begin{align} \Ex{\normtwo{\Sigma^{-1/2}X(\hat{\beta}-\beta)}^2} &= \Tr(\Ex{(Pv + \eta)^\T \Sigma^{-1}X (X^\T \Sigma^{-1}X)^{-1}X^\T \Sigma^{-1}(Pv + \eta)})\\ &= \Tr(\Ex{\Sigma^{-1}X (X^\T \Sigma^{-1}X)^{-1}X^\T \Sigma^{-1}(Pv + \eta)(Pv + \eta)^\T }) \end{align}\] This is equivalent to: \[\require{physics} \begin{align} &= \Tr(\varEx{X}{\Ex{\Sigma^{-1}X (X^\T \Sigma^{-1}X)^{-1}X^\T \Sigma^{-1}\vert X} \Ex{(Pv + \eta)(Pv + \eta)^\T \vert X})}\\ &= \Tr(\varEx{X}{\Sigma^{-1}X (X^\T \Sigma^{-1}X)^{-1}X^\T \Sigma^{-1}\Sigma)}\\ &= \Tr(\varEx{X}{ (X^\T \Sigma^{-1}X)^{-1}X^\T\Sigma^{-1}X)}\\ &= \Tr(I_d) = d. \end{align}\] ◻

Proof. First, lets apply the Bayes’ rule in its canonical form: \[\begin{align} \log p(\beta\mid y) = -\tfrac12\,(y-X\beta)^{\top}\Sigma^{-1}(y-X\beta) -\tfrac12\,\beta^{\top}\Lambda_0\,\beta +\text{const}. \end{align}\] Then, we can expand the quadratic in \(y-X\beta\) to get: \[\begin{align} (y-X\beta)^{\top}\Sigma^{-1}(y-X\beta) = y^{\top}\Sigma^{-1}y -2\beta^{\top}X^{\top}\Sigma^{-1}y +\beta^{\top}X^{\top}\Sigma^{-1}X\,\beta . \end{align}\] Hence, we can conclude \[\begin{align} \log p(\beta\mid y) = -\tfrac12\Bigl[ \beta^{\top}\bigl(X^{\top}\Sigma^{-1}X+\Lambda_0\bigr)\beta -2\beta^{\top}X^{\top}\Sigma^{-1}y \Bigr] +\text{const} \end{align}\] Next, we apply “completing the squares” trick, where we subtract and add \(y^\top \Sigma^{-1} X (X^\top \Sigma^{-1} X + \Lambda_0)^{-1}X^\top \Sigma^{-1} y\). Note that this term does not contain \(\beta\). So, we can treat it as a constant when computing \(\log p (\beta \mid X, y)\).

\[\begin{align} \log p(\beta\mid y) &= -\tfrac12\Bigl[ \beta^{\top}\bigl(X^{\top}\Sigma^{-1}X+\Lambda_0\bigr)\beta \nonumber \\ & -2\beta^{\top}X^{\top}\Sigma^{-1}y +y^\top \Sigma^{-1} X (X^\top \Sigma^{-1} X + \Lambda_0)^{-1}X^\top \Sigma^{-1} y \Bigr] +\text{const}. \label{eq:801} \end{align}\tag{23}\] For simplicity of calculations lets first define: Define the posterior precision \[\Lambda_{\mathrm{post}} := X^{\top}\Sigma^{-1}X+\Lambda_0, \quad \mu_\mathrm{post} := \Lambda_{\mathrm{post}}^{-1}X^{\top}\Sigma^{-1}y .\]

Substituting the above into 23 yields: \[\begin{align} \log p(\beta\mid y) = -\tfrac12\,(\beta-\mu_\mathrm{post})^{\top}\Lambda_{\mathrm{post}}\,(\beta-\mu_\mathrm{post}) +\text{const}, \end{align}\] since \(\Lambda_{\mathrm{post}}\mu_\mathrm{post}=X^{\top}\Sigma^{-1}y\).

The above posterior distribution over \(\beta \mid X, y\) matches the functional form of a Gaussian distribution \(\beta\mid y \;\sim\; \mathcal{N}\!\bigl(\mu_\mathrm{post},\;\Lambda_{\mathrm{post}}^{-1}\bigr)\) with mean: \[\mu_\mathrm{post} = \bigl(X^{\top}\Sigma^{-1}X+\Lambda_0\bigr)^{-1} X^{\top}\Sigma^{-1}y,\] ◻

Proof. Matching the form of \(\Ex{\beta \mid X, y}\) to that in Lemma 18, we need to show: \(X^\top \Sigma^{-1}X = \frac{1}{\sigma^2} X^\top X - \frac{1}{\sigma^4} SWS\), and \(X^\top \Sigma^{-1} y = \frac{1}{\sigma^2} X^\top y - \frac{1}{\sigma^4} SWX_\pub^\top y_\pub\). We first rewrite the noise covariance so that the Woodbury identity applies. Let \[\begin{align} U \;:=\; \begin{bmatrix} X_{\text{pub}}\\[2pt]0 \end{bmatrix}\!, \qquad C\;:=\;\frac{\tau^{2}}{d}I_d, \end{align}\] This means that our \(\Sigma\) matrix is given by: \[\begin{align} \Sigma=\sigma^{2}I_{m+n}+UC\,U^{\top}. \end{align}\] Applying Woodbury to the above we get, \[\begin{align} \Sigma^{-1} =\frac{1}{\sigma^{2}}I_{m+n} -\frac{1}{\sigma^{4}}\, U\!\mathopen{}\mathclose{\left(C^{-1}+\sigma^{-2}U^{\top}U}\right)^{\!-1}\!U^{\top}. \end{align}\]

Because \(U^{\top}U=X_{\text{pub}}^{\top}X_{\text{pub}}=:S\), we define \(W\) as \[\begin{align} W\;:=\; \mathopen{}\mathclose{\left(\frac{d}{\tau^{2}}I_d+\sigma^{-2}S}\right)^{\!-1}, \end{align}\] this abbreviates the inverse above and yields \[\Sigma^{-1} =\frac{1}{\sigma^{2}}I -\frac{1}{\sigma^{4}}U W U^{\top}.\]

With the above calculations, we start with the matrix term \(X^\top\Sigma^{-1}X\), \[\begin{align} X^{\top}\Sigma^{-1}X &=\frac{1}{\sigma^{2}}X^{\top}X -\frac{1}{\sigma^{4}}X^{\top}UWU^{\top}X \\ &=\frac{1}{\sigma^{2}}X^{\top}X -\frac{1}{\sigma^{4}}SWS . \end{align}\] This matches the definition of \(M\) in the statement of Lemma 19. \[M \;=\; \frac{1}{\sigma^{2}}X^{\top}X -\frac{1}{\sigma^{4}}SWS .\]

Next, we look at the vector term \(X^\top \Sigma^{-1}y\). \[\begin{align} X^{\top}\Sigma^{-1}y &=\frac{1}{\sigma^{2}}X^{\top}y -\frac{1}{\sigma^{4}}X^{\top}UWU^{\top}y \\ &=\frac{1}{\sigma^{2}}X^{\top}y -\frac{1}{\sigma^{4}}SWX_{\text{pub}}^{\top}y_{\text{pub}} . \end{align}\] This matches the \(m\) term in the statement of Lemma 19. \[m \;=\; \frac{1}{\sigma^{2}}X^{\top}y -\frac{1}{\sigma^{4}}SWX_{\text{pub}}^{\top}y_{\text{pub}} .\]

Plugging this into the posterior mean for \(\beta\), we get: \[\mathbb{E}[\beta\mid X,y] =(X^{\top}\Sigma^{-1}X+bI_d)^{-1}X^{\top}\Sigma^{-1}y =(M+bI_d)^{-1}m .\] ◻

Proof. We have \(\tilde{\Lambda} = \bigl(X^{\top}\Sigma^{-1}X+\Lambda_0\bigr)\) where we set \(\Lambda_0 = bI_d\) for some \(b\). Using the previous transformations,

\[\begin{align} \tilde{\Lambda} = \mathopen{}\mathclose{\left(\frac{1}{\sigma^2}X^\T X - \frac{1}{\sigma^4}X_\pub^\T X_\pub (\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub + bI_d }\right) \end{align}\]

To bound the spectral norm, we will use a series of transformations to express the spectral norm in terms of eigenvalues of the matrices in the expression.

We have \[\begin{align} \normtwo{\tilde{\Lambda}^{-1}} = \frac{1}{\lambda_{\min}\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}X^\T X - \frac{1}{\sigma^4}X_\pub^\T X_\pub (\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub + bI_d }\right)} \end{align}\] (Note that we will eventually take the expectation over the fourth power.)

We want to upper bound this quantity which involves lower bounding the denominator.

Weyl’s inequality gives that \(\lambda_{\min}(A-B) \geq \lambda_{\min}(A) - \lambda_{\max}(B)\) for real symmetric \(A\) and \(B\). Moreover, the original expression \(\tilde{\Lambda}\) is PSD and therefore the eigenvalues are lower bounded by 0, giving a stronger guarantee than the Weyl lower bound. Hence, \[\begin{align} &\lambda_{\min}\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}X^\T X - \frac{1}{\sigma^4}X_\pub^\T X_\pub (\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub + bI_d }\right) \\ &= \lambda_{\min}\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}X^\T X - \frac{1}{\sigma^4}X_\pub^\T X_\pub (\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub }\right) + b \\ &\geq \max\mathopen{}\mathclose{\left(0, \lambda_{\min}\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}X^\T X }\right) - \lambda_{\max}\mathopen{}\mathclose{\left(\frac{1}{\sigma^4}X_\pub^\T X_\pub (\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub }\right)}\right) + b. \end{align}\]

Focusing now on the last term, which we want to upper bound in order to lower bound the previous expression: \[\begin{align} &\lambda_{\max}\mathopen{}\mathclose{\left(\frac{1}{\sigma^4}X_\pub^\T X_\pub (\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub}\right) \\ &= \normtwo{\mathopen{}\mathclose{\left(\frac{1}{\sigma^4}X_\pub^\T X_\pub (\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}X_\pub^\T X_\pub}\right)} \\ &\leq \frac{1}{\sigma^4}\normtwo{X_\pub^\T X_\pub}^2 \normtwo{(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}} \end{align}\] The last line follows from the submultiplicativity of operator norm.

Bounding even further, \[\begin{align} \normtwo{(\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub)^{-1}} &= \frac{1}{\lambda_{\min}((\frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub))}\\ &= \frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\lambda_{\min}(X_{\pub}^\T X_\pub)}. \end{align}\]

Putting it all together, we arrive at: \[\begin{align} \normtwo{\tilde{\Lambda}^{-1}} \leq \frac{1}{\max\mathopen{}\mathclose{\left(0, \frac{1}{\sigma^2}\lambda_{\min}(X^\T X) - \frac{1}{\sigma^4}\normtwo{X_\pub^\T X_\pub}^2 \frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\lambda_{\min}(X_{\pub}^\T X_\pub)}}\right) + b} \end{align}\] Note \(\normtwo{X_\pub^\T X_\pub} = \lambda_{\max}(X_\pub^\T X_\pub)\). We now have the expression in terms of min and max eigenvalues of \(X^\T X\) and \(X_\pub^\T X_\pub\).

Moreover since the expression is positive and monotonic, we also have \[\begin{align} \normtwo{\tilde{\Lambda}^{-1}}^4 \leq \frac{1}{\mathopen{}\mathclose{\left(\max\mathopen{}\mathclose{\left(0, \frac{1}{\sigma^2}\lambda_{\min}(X^\T X) - \frac{1}{\sigma^4}\normtwo{X_\pub^\T X_\pub}^2 \frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\lambda_{\min}(X_{\pub}^\T X_\pub)}}\right) + b}\right)^4}. \end{align}\]

This expression is upper bounded by \(1/b^4\) when the \(\max\) term goes to 0.

To bound this, we will do something similar to the non-shifted setting but instead of bounding a single constant \(c\), we will instead want to bound the three eigenvalue terms with \(t_1, t_2, t_3 > 0\). (Note that all the involved matrices are PSD.) Specifically: Let \(\lambda_1 := \lambda_{\min}(X^\T X)\), \(\lambda_2 := \lambda_{\max}(X_\pub^\T X_\pub)\), \(\lambda_3 := \lambda_{\min}(X_{\pub}^\T X_\pub)\). Then

\[\begin{align} &\Ex{\normtwo{\tilde{\Lambda}^{-1}}^4} \\ &=\Ex{\normtwo{\tilde{\Lambda}^{-1}}^4 \vert \lambda_1 \in [t_1, \infty) \wedge \lambda_2 \in [0, t_2] \wedge \lambda_3 \in [t_3, \infty)} \nonumber\\ &\quad\quad\quad\quad \cdot \Pr\mathopen{}\mathclose{\left( \lambda_1 \in [t_1, \infty) \wedge \lambda_2 \in [0, t_2] \wedge \lambda_3 \in [t_3, \infty) }\right) \\ &+\Ex{\normtwo{\tilde{\Lambda}^{-1}}^4 \vert \lambda_1 \in [0, t_1) \vee \lambda_2 \in (t_2, \infty) \vee \lambda_3 \in [0, t_3)} \nonumber \\ &\quad\quad\quad\quad \cdot \Pr\mathopen{}\mathclose{\left( \lambda_1 \in [0, t_1) \vee \lambda_2 \in (t_2, \infty) \vee \lambda_3 \in [0, t_3) }\right) \end{align}\]

Again, we will coarsely upper bound the first probability by 1 and use a union over tail bounds to bound the second probability. \[\begin{align} &\leq \frac{1}{\max(0, \frac{1}{\sigma^2}t_1 - \frac{1}{\sigma^4}t_2^2 \frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}t_3}) + b)^4} + \frac{1}{b^4} \Pr\mathopen{}\mathclose{\left( \lambda_1 \in [0, t_1) \vee \lambda_2 \in (t_2, \infty) \vee \lambda_3 \in [0, t_3) }\right) \end{align}\]

We will eventually want \(t_1 = \Omega(N), t_2 = O(m), t_3 = \Omega(m)\), and we would like the second union over tail bounds to be vanishingly small. Following Lemma 10 and  11, we set \(t_1 = N(1 - \sqrt{d/N} - \psi)^2\), \(t_2 = m(1 + \sqrt{d/m} + \psi)^2\), and \(t_3 = m(1-\sqrt{d/m} - \psi)^2\). We assume \(n, m > 100d\) and set \(\psi = 1/10\) in all cases. The lemmas then give \(t_1 > 63/100 \cdot N, t_2 < 64/100 \cdot m, t_3 > 63/100 \cdot m\).

We can lastly confirm that with these values of \(t_1, t_2, t_3\) we can drop the \(\max\) in the denominator of the first term, as follows: \[\begin{align} \frac{1}{\sigma^2}t_1 - \frac{1}{\sigma^4}t_2^2 \frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}t_3} \geq \frac{1}{\sigma^2}\frac{63}{100}N - \frac{1}{\sigma^4}(\frac{64}{100}m)^2 \frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}(63/100)m} \maybegt 0\\ \end{align}\]

Since \(d/\tau^2 > 0\), \[\begin{align} \frac{1}{\sigma^2}\frac{63}{100}N - \frac{1}{\sigma^4}(\frac{64}{100}m)^2 \frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}(63/100)m} > \frac{1}{\sigma^2}\frac{63}{100}N - \frac{1}{\sigma^4}(\frac{64}{100}m)^2 \frac{1}{\frac{1}{\sigma^2}(63/100)m} \maybegt 0 \end{align}\]

Omitting algebra, and noting that \(N = n+m\), this leads to the condition \[\begin{align} n > ((64/100)^2(100/63) - 1)m = -0.349m \end{align}\] which is true. Given that this term is therefore strictly greater than 0 for the values of \(t_1, t_2, t_3\) we have chosen, we can drop the \(\max(0, \cdot)\).

We can then bound the relevant tail probabilities using Lemma 8, Lemma 9, and Fact 14 and take a union bound to conclude that \[\Pr\mathopen{}\mathclose{\left( \lambda_1 \in [0, t_1) \vee \lambda_2 \in (t_2, \infty) \vee \lambda_3 \in [0, t_3) }\right) = \gO\mathopen{}\mathclose{\left(\frac{1}{N^8}}\right).\]

Thus, we have \[\begin{align} \Ex{\normtwo{\tilde{\Lambda}^{-1}}^4} \leq O\mathopen{}\mathclose{\left(\frac{1}{(\frac{1}{\sigma^2}N - \frac{1}{\sigma^4}m^2 \frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m} + b)^4}}\right) + O\mathopen{}\mathclose{\left(\frac{1}{b^4N^8}}\right) \end{align}\] and the first term dominates, giving the result. ◻

Proof. Using the block-diagonal structure of \(\Sigma\) (and therefore \(\Sigma^{-1}\)), we can decompose \(X^\T \Sigma^{-1}y\) into \(X_{\pub}^\T \Sigma_{\pub}^{-1} y_\pub + X_\priv^\T \Sigma_{\priv}^{-1}y_\priv\). (\(\Sigma_\pub\) is the upper-left block of \(\Sigma\) corresponding to public data and \(\Sigma_\priv\) the corresponding lower-right block for private data.) Here, \(\Sigma_{\priv}^{-1}\) is simply \(\frac{1}{\sigma^2}I_n\), so we can reuse the upper bound from Lemma 14 with an additional factor of \(\frac{1}{\sigma^8}\).

The term incorporating public data is more complicated.

We first note the following useful transformation (applying the Woodbury identity only to \(\Sigma_\pub^{-1}\)): \[\begin{align} \Sigma_\pub^{-1} = \frac{1}{\sigma^2}I_m - \frac{1}{\sigma^4}X_\pub\mathopen{}\mathclose{\left( \frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X_\pub^\T X_\pub }\right)^{-1}X_\pub^\T. \end{align}\]

Note: For notational convenience, in the following, we will drop the “\(\mathrm{pub}\)” term from the subscript since we only need to bound \(X_\pub ^\top \Sigma^{-1}_\pub y_\pub\).

We will use the following bound in several places: \[\begin{align} \Ex{\normtwo{X^\T\Sigma^{-1}X}^4} &\leq \Ex{\normtwo{X^\T \mathopen{}\mathclose{\left( \frac{1}{\sigma^2}I_m - \frac{1}{\sigma^4}X\mathopen{}\mathclose{\left( \frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X^\T X }\right)^{-1}X^\T }\right) X}^4}\\ &= \Ex{\normtwo{\frac{1}{\sigma^2}X^\T X - \frac{1}{\sigma^4}X^\T X\mathopen{}\mathclose{\left( \frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X^\T X }\right)^{-1}X^\T X}^4}\\ &\leq \Ex{\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}\normtwo{X^\T X} - \frac{1}{\sigma^4} \lambda_{\min}\mathopen{}\mathclose{\left(X^\T X\mathopen{}\mathclose{\left( \frac{d}{\tau^2}I_d + \frac{1}{\sigma^2}X^\T X}\right)^{-1}X^\T X}\right) }\right)^4}\\ &\leq \Ex{\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}\normtwo{X^\T X} - \frac{1}{\sigma^4} \lambda_{\min}(X^\T X)^2\frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\normtwo{X^\T X}}}\right)^4} \end{align}\]

Note that the third inequality follows from the fact that \(X^\top \Sigma^{-1} X \succeq 0\), so we can upper bound the full term by applying an upper bound on the term within \((\cdot)^4\) since the term inside it is always positive. Next, we can break the expectation into two conditional expectations. \[\begin{align} & \Ex{\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}\normtwo{X^\T X} - \frac{1}{\sigma^4} \lambda_{\min}(X^\T X)^2\frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\normtwo{X^\T X}}}\right)^4} \\ &\leq \Ex{\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}\normtwo{X^\T X} - \frac{1}{\sigma^4} \lambda_{\min}(X^\T X)^2\frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\normtwo{X^\T X}}}\right)^4 \mid \lambda_{\min}(X^\top X) \geq t_1, \lambda_{\max}(X^\top X) \leq t_2} \\ & \quad\quad\quad\quad \cdot \Pr\paren{\lambda_{\min}(X^\top X) \geq t_1 , \lambda_{\max}(X^\top X) \leq t_2} \end{align}\]

Using Lemma 8, we can upper bound the above expression by applying a high probability tail bound on \(\lambda_{\min}(X^\top X)\). When \(N \geq 100d\), then with constant probability \(\lambda_{\min} (X^\top X) = m - \Omega(1)\) and \(\lambda_{\max} (X^\top X) = m - \gO(1)\). Plugging this result into the above expression, we conclude:

\[\begin{align} \Ex{\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}\normtwo{X^\T X} - \frac{1}{\sigma^4} \lambda_{\min}(X^\T X)^2\frac{1}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}\normtwo{X^\T X}}}\right)^4} &\leq \mathopen{}\mathclose{\left(\frac{1}{\sigma^2}m - \frac{1}{\sigma^4}\frac{m^2}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m}}\right)^4. \end{align}\]

When \(\tau \to 0\) the term \(\|X^\top \Sigma^{-1} X \beta\|^4\) goes to \(m^4\) (giving the correct contribution of \(m^4d^2\) when combined with the contribution of \(\beta\)) and when \(\tau \to \infty\) the second part of the term cancels sending the public sample contribution to 0.

Once again, we decompose the term \[\begin{align} \Ex{\normtwo{X^\T \Sigma^{-1} y}^4} &= \Ex{\normtwo{X^\T\Sigma^{-1}X\beta + Xv + \eta)}^4}\\ &\leq \Ex{\normtwo{X^\T\Sigma^{-1}X\beta}^4} + \Ex{\normtwo{X^\T\Sigma^{-1}(Xv + \eta)}^4}\\ &\leq \Ex{\normtwo{X^\T\Sigma^{-1}X\beta}^4} + \Ex{\normtwo{X^\T\Sigma^{-1}Xv}^4} + \Ex{\normtwo{X^\T \Sigma^{-1}\eta}^4}\\ &\leq \Ex{\normtwo{X^\T\Sigma^{-1}X}^4\normtwo{\beta}^4} + \Ex{\normtwo{X^\T\Sigma^{-1}X}^4\normtwo{v}^4} + \Ex{\normtwo{X^\T \Sigma^{-1}}^4\normtwo{\eta}^4}\\ &= \Ex{\normtwo{X^\T\Sigma^{-1}X}^4}\Ex{\normtwo{\beta}^4} + \\ &\quad \;\Ex{\normtwo{X^\T\Sigma^{-1}X}^4}\Ex{\normtwo{v}^4} + \Ex{\normtwo{X^\T \Sigma^{-1}}^4}\Ex{\normtwo{\eta}^4} \end{align}\]

Since \(\beta \sim \cal{N}(0, \frac{1}{b}I_d)\) we have \(\Ex{\normtwo{\beta}^4} \leq d^2/b^2\). Similarly, for \(v \sim \cal{N}(0, I_d)\) we have \(\Ex{\normtwo{v}} \leq d^2\). Finally, \(\eta \sim \cal{N}(0, I_m)\) gives \(\Ex{\normtwo{\eta}} \leq m^2\).

We also need the following bound: \[\begin{align} \Ex{\normtwo{X^\T \Sigma^{-1}}^4} &\leq \Ex{\normtwo{X}^4\normtwo{\Sigma^{-1}}^4} \end{align}\] From Gordon’s theorem [52] we have \(\Ex{\normtwo{X}^4} \leq (\sqrt{m} + \sqrt{d})^4 \leq 8(m^2 + d^2)\). With a small variation on the earlier analysis of \(X^\T \Sigma^{-1}X\), bounding \(\normtwo{X}^2 \leq (\sqrt{m} + \sqrt{d})^2\) using Gordon’s theorem, we also have \(\Ex{\normtwo{\Sigma^{-1}}^4} \leq \mathopen{}\mathclose{\left(\frac{1}{\sigma^2} - \frac{1}{\sigma^4}\frac{(\sqrt{m} + \sqrt{d})^2}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m}}\right)^4 \leq \mathopen{}\mathclose{\left(\frac{1}{\sigma^2} - \frac{1}{\sigma^4}\frac{O(m)}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m}}\right)^4\).

Overall, this gives: \[\begin{align} &\Ex{\normtwo{X^\T \Sigma^{-1} y}^4} \leq O\bigl( \frac{1}{\sigma^8}(n^2d^2 + n^4d^2/b^2) + \\ &\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}m - \frac{1}{\sigma^4}\frac{m^2}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m}}\right)^4(d^2/b^2 + d^2) + \mathopen{}\mathclose{\left( \frac{1}{\sigma^2} - \frac{1}{\sigma^4}\frac{m}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m} }\right)^4(m^2 + d^2)(m^2) \bigr). \end{align}\] The first two terms follow from using Lemma 14 with only private samples (as they are not shifted and the same bound applies).

We can simplify, combining the first two terms and dropping lower-order terms (note that we assume \(m \gg d\)) to arrive at a form that will later be more convenient: \[\begin{align} &\leq \gO\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}(n+m) - \frac{1}{\sigma^4}\frac{m^2}{\frac{d}{\tau^2} + \frac{1}{\sigma^2}m}}\right)^4(d^2/b^2 + d^2)}\right). \end{align}\] ◻

Proof. Recall that \(\hat{\beta}\) is the GLS estimator, where \(\hat{\beta} = (X^\top \Sigma^{-1} X)^{-1} X^\top \Sigma^{-1} y\). Throughout the proof, we assume \(d, n \gg d\), and that the matrix \(X^\top \Sigma^{-1} X\) is full rank with constant probability.

Let \(\Lambda \eqdef X^\top \Sigma^{-1} X\). Fixing \(\beta\), and taking the expectation over \(X, y\), we can simplify the expression as follows: \[\begin{align} \Ex{\normtwo{\hat{\beta} - \beta}^2} &= \Ex{ \|(X^\top \Sigma^{-1} X)^{-1} X^\top \Sigma^{-1} y - \beta \|^2_2} \nonumber \\ &= \Ex{\|\Lambda^{-1} X^\top \Sigma^{-1} y - \Lambda^{-1}\Lambda \beta\|_2^2} \nonumber \\ & \leq \Ex{\|\Lambda^{-1} ( X^\top \Sigma^{-1} (X\beta + \eta) - \Lambda \beta)\|_2^2} \nonumber \\ & = \Ex{\|\Lambda^{-1} ( X^\top \Sigma^{-1} (X\beta + \eta) - X^\top \Sigma^{-1} X \beta)\|_2^2} \nonumber \\ & = \Ex{\|\Lambda^{-1} ( X^\top \Sigma^{-1} \eta)\|_2^2} \end{align}\]

\[\begin{align} \mathbb{E} \bigl[\lVert\Lambda^{-1}X^{\top}\Sigma^{-1}\eta\rVert_2^{2}\bigr] &=\mathbb{E}_{X} \Bigl[\, \lVert\Lambda^{-1}\rVert_2^{2}\; \mathbb{E}_{\eta} \bigl[\lVert X^{\top}\Sigma^{-1}\eta\rVert_2^{2}\mid X\bigr] \Bigr] \tag{24}\\ &=\mathbb{E}_{X}\!\Bigl[\, \lVert\Lambda^{-1}\rVert_2^{2}\; \operatorname{tr}\!\bigl(X^{\top}\Sigma^{-1}\Sigma\Sigma^{-1}X\bigr) \Bigr] \nonumber\\ &=\mathbb{E}_{X}\!\Bigl[\, \lVert\Lambda^{-1}\rVert_2^{2}\;\operatorname{tr}(\Lambda) \Bigr], \tag{25} \end{align}\] where the second equality follows from the fact that \(\Ex{\eta\eta^\top \mid X} = \Sigma\). Since \(\lVert\Lambda^{-1}\rVert_2^{2}=1/\lambda_{\min}(\Lambda)^{2}\) and \(\operatorname{tr}(\Lambda)\le d\,\lambda_{\max}(\Lambda)\), \[\begin{align} \lVert\Lambda^{-1}\rVert_2^{2}\,\operatorname{tr}(\Lambda) \;\le\; \frac{d\,\lambda_{\max}(\Lambda)}{\lambda_{\min}(\Lambda)^{2}} . \label{eq:182} \end{align}\tag{26}\] For Gaussian designs whitened by \(\Sigma^{-1/2}\) one has, with constant probability, \[\begin{align} \lambda_{\min}(\Lambda)=\Omega\!\bigl(n+m/\kappa\bigr), \qquad \lambda_{\max}(\Lambda)=O\!\bigl(n+m/\kappa\bigr). \label{eq:183} \end{align}\tag{27}\] Substituting 27 into 26 and taking expectations, \[\mathbb{E}\!\bigl[\lVert\hat{\beta}-\beta\rVert_2^{2}\bigr] \;\le\; C\, \frac{d\,(n+m/\kappa)}{\bigl(n+m/\kappa\bigr)^{2}} \;=\; O\!\Bigl(\tfrac{d}{\,n+m/\kappa\,}\Bigr),\] for an absolute constant \(C>0\). This concludes the proof. ◻

Proof. Let \(\gamma(\tau) = d/\tau^2 + m/\sigma^2\). Note that when \(\tau \to \infty\), \(\gamma(\tau)\) approaches \(m/\sigma^2\) (such that \(m/\sigma^2 - \frac{1}{\gamma(\tau)} \to 0\) negating the effect of public samples), and when \(\tau \to 0\), \(\gamma(\tau) \to \infty\) (such that \(m/\sigma^2 - \frac{1}{\gamma(\tau)} \to m/\sigma^2\) so that public and private samples contribute equally).

From Lemma 20 and Lemma 21, we derive the following: \[\begin{align} & \sqrt{\mathbb{E}_{X,\eta} \mathbb{E}_{\hat{\beta}} \mathopen{}\mathclose{\left\| M(X,y) - \hat{\beta} }\right\|_2^2 \cdot \sqrt{b^4\Ex{\normtwo{\tilde{\Lambda}^{-1}}^4}\Ex{\normtwo{X^\T \Sigma^{-1}y}^4}}} \end{align}\] We first simplify just the inner square root. Using the previous lemmas and applying the identity \(\sqrt{x+y} \leq C \cdot(\sqrt{x} + \sqrt{y})\): \[\begin{align} &\leq b^2 \gO\mathopen{}\mathclose{\left(\frac{1}{(\frac{1}{\sigma^2}N - \frac{1}{\sigma^4}\frac{m^2}{\gamma(\tau)} + b)^2}}\right) \sqrt{\gO\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}N - \frac{1}{\sigma^4}\frac{m^2}{\gamma(\tau)}}\right)^4(d^2/b^2 + d^2)}\right)}\\ &\leq b^2 \gO\mathopen{}\mathclose{\left(\frac{1}{(\frac{1}{\sigma^2}N - \frac{1}{\sigma^4}\frac{m^2}{\gamma(\tau)} + b)^2}}\right) \gO\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}N - \frac{1}{\sigma^4}\frac{m^2}{\gamma(\tau)}}\right)^2(d/b + d)}\right)\\ &\leq b^2 \gO\mathopen{}\mathclose{\left(\frac{1}{(\frac{1}{\sigma^2}N - \frac{1}{\sigma^4}\frac{m^2}{\gamma(\tau)})^2}}\right) \gO\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left(\frac{1}{\sigma^2}N - \frac{1}{\sigma^4}\frac{m^2}{\gamma(\tau)}}\right)^2(d/b + d)}\right) \end{align}\]

Substituting \(b=1/d\) and making cancellations: \[\begin{align} &\leq (d^2 + d)/d^2 \leq 1 + 1/d \end{align}\]

Finally, we substitute into the original expression, combining with Lemma 22 (recall that \(\kappa = m\tau^2/d + 1\) and \(\alpha = \gO(1)\)): \[\begin{align} & \sqrt{\mathbb{E}_{X,\eta} \mathbb{E}_{\hat{\beta}} \mathopen{}\mathclose{\left\| M(X,y) - \hat{\beta} }\right\|_2^2 \cdot \sqrt{b^4\Ex{\normtwo{\tilde{\Lambda}^{-1}}^4}\Ex{\normtwo{X^\T \Sigma^{-1}y}^4}}}\\ &\leq \sqrt{\mathopen{}\mathclose{\left(\gO\paren{\frac{d}{n+m/\kappa}} + \alpha^2}\right) \cdot \gO(1 + 1/d)} = \gO(1) \end{align}\]

since \(\alpha^2 = \gO(1)\). ◻