The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches

We thank the reviewer for highlighting the significance of our new analysis and for acknowledging the strength of our theoretical contributions.

We also appreciate the comment regarding clarity and agree that some statements in the current version may be difficult to follow. In the revised version, we will revise the text to improve clarity and readability, as suggested.

Regarding the questions raised:

1. As noted in the text, both the pink and red curves represent our newly developed analysis. The only substantive difference between the algorithm proposed in our work and the baseline in [1, 2] lies in how the smallest eigenvalue, $\lambda_{\min}((X, Y)^{\top}(X, Y))$, is estimated and used. In particular, when $\lambda_{\min}((X, Y)^{\top}(X, Y))$ is close to zero, the two versions behave similarly. Thus, the pink and red curves often overlap, with slight differences attributed to the different privacy parameter allocation throughout the algorithm. We emphasize that both variants stem from contributions introduced in our work, not from the results of [1].

2. The method referred to by the reviewer, known as output perturbation, can provide reasonably good private solutions under certain technical conditions (see, for example, [2, 4]). However, for private linear regression, the AdaSSP algorithm from [3] achieves the strongest guarantees on both empirical and test risk under minimal assumptions and is widely regarded as the leading baseline in this setting. For this reason, we selected AdaSSP as our baseline for the linear regression experiments.

   For the logistic regression simulations, however, the output perturbation technique is generally considered less effective than the widely adopted objective perturbation approach (see, e.g., the discussions in [2] and [4]). For this reason, we selected objective perturbation as the primary baseline in our logistic regression experiments. To further strengthen our empirical comparison, we have included an additional DP-SGD baseline in this rebuttal (see the table below), which we also plan to incorporate into the final version of the manuscript.

[1] Sheffet, Or. ``Differentially private ordinary least squares." International Conference on Machine Learning. PMLR, 2017.

[2] Kifer, Daniel, Adam Smith, and Abhradeep Thakurta. ``Private convex empirical risk minimization and high-dimensional regression." Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 2012.

[3] Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction & estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 93–103. AUAI Press, 2018.

[4] Chaudhuri, Kamalika, Claire Monteleoni, and Anand D. Sarwate. "Differentially private empirical risk minimization." Journal of Machine Learning Research 12.3 (2011).

We thank the reviewer for their detailed and thoughtful feedback. We aim to address the points raised below.

Differentiation from [1, 2]:

• Privacy Analysis via RDP:

While [1,2] analyze a variant of the Gaussian mixing mechanism using classical $(\varepsilon,\delta)$-DP techniques, our analysis leverages the RDP framework and leads to the following theoretical insights:

1. The RDP-based approach yields tighter bounds on the privacy parameters of the Gaussian mixing mechanism. These tighter guarantees directly translate into improved utility when applied to private linear regression.

2. We prove that the Gaussian mixing mechanism satisfies tCDP, a fact that was not known prior to our work. Moreover, and perhaps more surprisingly, this finding provides a novel example of a mechanism with a data-dependent covariance matrix that satisfies tCDP. Notably, such behavior is not exhibited by previously known mechanisms with data-dependent parameters that satisfy tCDP, such as the Gaussian smooth sensitivity.

3. For certain datasets $X$, our bounds are achieved with equality, giving a tight characterization of the privacy guarantees of the Gaussian mixing mechanism. As a direct consequence of our analysis, for input matrices $X$ such that $\underset{i\in [n]}{\sup} ||x_i||^2 \leq C_X^2$ and $\lambda\_{\min}(X^{\top}X) \geq C_X^2$, our bound is achieved with equality when $\frac{1}{C_X}X$ is semi-orthogonal. In particular, in this case, it holds that $\underset{i \in [n]}{\sup} \ x_i^\top (X^\top X + \sigma^2 \mathbf{I}_d)^{-1} x_i = \frac{C_X^2}{\sigma^2 + C_X^2}$ and all inequalities in our analysis are achieved with equality, resulting in tight privacy guarantees.

• Utility Guarantees for Gaussian Mixing in Private Linear Regression:

As a second theoretical contribution, we establish a formal utility guarantee for an algorithm that employs Gaussian mixing to perform private linear regression. This provides a meaningful extension beyond prior analyses in [1,2], which also connects to the utility theorem presented in [3].

The current version of our work deliberately places greater emphasis on the refined privacy analysis, which is the central focus of this paper. An ongoing extension of this work aims to build upon our current utility analysis (Theorem 3) by providing a more detailed and rigorous utility comparison to complement our existing privacy results.

Intuition for Empirical Improvements:

An intuition for these results can be formalized as follows:

1. Compared to the algorithms in [1, 2], our method provides tighter privacy guarantees and is therefore expected to yield strictly better performance in private linear regression tasks. To see this, note that for a fixed value of $\gamma$ (corresponding to a fixed noise level), the privacy parameter $\varepsilon$ achieved by our method is smaller whenever the condition$\frac{\sqrt{k}}{\gamma} < 2\sqrt{2\log(1/\delta)} + \frac{4\log(4/\delta)}{\sqrt{k}}$ is satisfied. As discussed in Section 4, the effective noise level in our scheme is given by $\frac{\gamma}{\sqrt{k}}$, which is typically much greater than one. This makes the above condition likely to hold in most practical settings. Consequently, for any fixed set of mechanism parameters, our method achieves a smaller $\varepsilon$—or equivalently, requires less noise to attain a given target $\varepsilon$—and is therefore expected to outperform the algorithm from [1, 2], as supported by our simulations.

2. Compared to the AdaSSP algorithm from [3], our current guarantees (presented in Theorem 3) align closely with those of AdaSSP in the regime where $\lambda_{\min}(X^{\top}X) \approx 0$. In this setting, both methods yield similar utility bounds. Notably, our method avoids the additional $\log(d^2/\varrho)$ dependence that appears in the AdaSSP analysis, and as such can provide improved guarantees—particularly when the parameter $\chi$ is small and $\varepsilon$ lies in a low to moderate privacy regime. This behavior is consistent with our empirical findings. In contrast, when $\lambda\_{\min}(X^{\top}X) \gg 0$, the analysis in [3] shows that AdaSSP enjoys a favorable inverse dependence on this eigenvalue, potentially leading to tighter bounds. Our method, on the other hand, relies on the minimum eigenvalue of the extended matrix $(X, Y)^{\top}(X, Y)$, which is always upper-bounded by $\lambda\_{\min}(X^{\top}X)$. Therefore, in the regime where $\lambda\_{\min}(X^{\top}X)$ is large while $\lambda\_{\min}((X, Y)^{\top}(X, Y))$ remains small, AdaSSP is expected to outperform our method. Lastly, there is a third regime, where both $\lambda\_{\min}(X^{\top}X) \gg 0$ and $\lambda\_{\min}((X,Y)^{\top}(X,Y)) \gg 0$. This situation arises when $Y$ is nearly orthogonal to the column space of $X$, such that the augmented matrix $(X, Y)$ is nearly full-rank. In this regime, the signal in $Y$ is poorly explained by $X$, and the underlying linear regression task becomes less meaningful and both methods perform poorly.

Main Theoretical Significance:

As highlighted earlier in our response, the core theoretical contribution of this work lies in the improved privacy analysis based on RDP and the conclusions it enables. This analysis yields not only tighter bounds on the privacy parameters of the Gaussian mixing mechanism but also a more nuanced characterization of its privacy behavior—both aspects that were not captured in prior work. Moreover, as our simulations show, this refined analysis is essential for allowing the sketching-based algorithm to compete effectively with AdaSSP.

[1] Sheffet, Or. ``Differentially private ordinary least squares." International Conference on Machine Learning (ICML) PMLR, 2017.

[2] Sheffet, Or. ``Old techniques in differentially private linear regression." Algorithmic Learning Theory (ALT) PMLR, 2019.

[3] Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction & estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 93–103. AUAI Press, 2018.

We thank the reviewer for their thoughtful comments and for recognizing the strength of our privacy analysis of the Gaussian mixing mechanism.

Throughout the paper, we have aimed to highlight the main contributions, namely our refined RDP-based analysis of the Gaussian mixing mechanism and its implications for improving the performance of sketching-based algorithms for private linear regression. To that end, our primary objective was not to conduct an exhaustive empirical comparison against all existing methods, but rather to provide consistent evidence that our approach yields improvements over standard baselines in regimes where earlier analyses (e.g., [1, 2]) could not. While we acknowledge that the empirical gains may appear modest in some cases, we believe that consistently outperforming AdaSSP—particularly in settings where prior methods fail to do so—is a meaningful empirical contribution of our work. Moreover, as noted in our paper, the method proposed in [1, 2] remains effective in certain scenarios. Therefore, we believe that the fact that our approach achieves consistent and substantial performance improvements over this baseline across all datasets is another empirical contribution.

Comments Related to Theoretical Analysis:

We agree that our mathematical analysis by itself is not novel. However, we believe that our key conceptual and technical insight is that the privacy properties of this mechanism can be better understood, and its guarantees improved when viewed through the lens of RDP. This perspective enables us to derive tighter bounds than those previously known, and, furthermore, leads to two additional theoretical contributions:

1. Our bounds yield a closed-form characterization of the privacy parameters for certain inputs. To see this, as a direct consequence of our analysis, for input matrices $X$ such that $\underset{i\in [n]}{\text{sup}} ||x_i||^2 \leq C_X^2$ and $\lambda\_{\min}(X^{\top}X) \geq C_X^2$, our bound is achieved with equality when $\frac{1}{C_X}X$ is semi-orthogonal. In particular, in this case, it holds that $\underset{i\in [n]}{\text{sup}} \ x_i^\top (X^\top X + \sigma^2 \mathbf{I}_d)^{-1} x_i = \frac{C_X^2}{\sigma^2 + C_X^2}$ and all the inequalities in our analysis are achieved with equality, leading to tight privacy guarantees.

2. Our analysis establishes that the Gaussian mixing mechanism is tCDP. Importantly, we show that using the conversion between tCDP to $(\varepsilon, \delta)$-DP yields tighter privacy bounds than a direct $(\varepsilon, \delta)$-DP analysis—an outcome that is not immediate or obvious. In contrast, prior works such as [1, 2] rely on direct $(\varepsilon, \delta)$-DP arguments and derive weaker privacy guarantees. Furthermore, the fact that the Gaussian mixing mechanism satisfies tCDP enables one to leverage a broad body of existing theoretical results developed for this class of mechanisms. As a further insight, our work provides an example of a mechanism with a data-dependent covariance that satisfies tCDP. This stands in contrast to previously studied examples, which involve only data-dependent variances (see [4, 6]). We believe this observation is both nontrivial and potentially impactful, as it opens the door to further extend the previous developments from [4, 6] towards using richer data-dependent structures.

In addition to the contributions previously discussed, we believe our results offer meaningful value to the differential privacy community—particularly given the widespread use of randomized sketches in the optimization literature. Our findings demonstrate that, in certain settings, sketching-based mechanisms can yield substantial improvements in both privacy-utility trade-offs and computational efficiency, outperforming several state-of-the-art baselines.

Comments Related to Significance of Empirical Results:

Our experimental results are designed to demonstrate the practical relevance of our improved privacy analysis, showing consistent utility gains across multiple linear regression tasks within the standard privacy regime of $\varepsilon \in [0.1, 10]$, a range widely accepted for $(\varepsilon, \delta)$-differential privacy. While we agree that the empirical gains might be small for certain cases, our focus was not the empirical study by itself but rather demonstrating that our method offers a mathematically rigorous refinement over the popular baselines introduced in [1, 2], and that it capable of achieving a non-trivial improvements over the widely used AdaSSP algorithm [5] in various settings. The ability of the Gaussian mixing mechanism to consistently outperform this strong baseline is, in our view, a meaningful contribution. Notably, this improvement holds uniformly across all datasets considered.

We will ensure that these contributions are more clearly emphasized in the revised manuscript and thank the reviewer again for raising these points.

[1] Sheffet, Or. ``Differentially private ordinary least squares." International Conference on Machine Learning (ICML) PMLR, 2017.

[2] Sheffet, Or. ``Old techniques in differentially private linear regression." Algorithmic Learning Theory (ALT) PMLR, 2019.

[3] Bun, Mark, et al. "Composable and versatile privacy via truncated CDP." Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (SOTC). 2018.

[4] Hendrikx, Hadrien, Paul Mangold, and Aurélien Bellet. "The relative Gaussian mechanism and its application to private gradient descent." International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 2024.

[5] Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction & estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 93–103. AUAI Press, 2018.

We appreciate the reviewer’s positive feedback and acknowledgment of our work’s strengths. Please find below our detailed responses to the points you raised.

We agree that DP-SGD is an important and widely used baseline in the literature, particularly due to its strong theoretical guarantees. To address your suggestion, we have extended our experiments to include DP-SGD as an additional baseline on two representative datasets. We selected a reasonable fixed set of DP-SGD hyperparameters to ensure a fair comparison without incurring additional privacy cost from hyperparameter tuning (which we view as a potential drawback of DP-SGD, especially compared to our proposed mechanism, which requires tuning only a single hyperparameter). As shown in the attached table, our method outperforms DP-SGD in terms of runtime, and in these specific settings, it also achieves higher test accuracy for some settings of $\epsilon$. We believe these results highlight the practical value of our method, particularly in scenarios where computational efficiency and simplicity are important considerations. We will add these additional simulations to the final version of our manuscript.

Regarding the other points raised by the reviewer:

1. Usage with $\lambda_{\min} > 0$: Our method can be applied in cases where $\lambda_{\min} > 0$, and does not necessarily require that this eigenvalue is zero. However, note that our approach relies on $\lambda_{\min}((X,Y)^{\top}(X,Y))$ rather than $\lambda_{\min}(X^{\top}X)$. The former tends to be small in settings where $\underset{\theta}{\min} ||Y - X\theta||^2$ is small. This distinction implies that our method is expected to outperform AdaSSP when $\lambda_{\min}(X^\top X)$ is small, whereas in regimes where this eigenvalue is large, the guarantees in [2] suggest that AdaSSP benefits more due to its inverse dependence on $\lambda_{\min}(X^\top X)$. To clarify this point and the setting simulated in our work, we have added a table below reporting the observed minimum eigenvalues across all simulation settings.

2. Tuning Private Embeddings: We appreciate your observation that our method can also be applied to fine-tune embeddings obtained non-privately. In this work, we followed the setup proposed in [1], which motivated the need for privately fine-tuning a logistic head. Our goal was to demonstrate the effectiveness of our approach in this setting, demonstrating its effectiveness in a commonly used setup.

[1] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In Proceedings of the International Conference on Machine Learning (ICML). JMLR.org, 2020.362

[2] Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction & estimation in unbounded domain. In Proc. 34th Conf. Uncertainty in Artif. Intell. (UAI), pages 93–404103. AUAI Press, 2018.