- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper studies the optimal Mean Squared Error (MSE) among additive mechanisms that guarantee that a quiery with a bounded sensitivity satisfies approximate differential privacy -DP. The authors introduce a new mechanism: closed-form generalized gamma mechanism (CGG), an efficient version of the recent spherical generalized gamma (SGG) mechanism [1]. The authors showed it to be optimal for the high-dimensional queries up to three asymptotic terms. Moreover, they provided a numerical comparison with the Gaussian mechanism, SGG and mechanisms [2].
[1] Y. Wei et al. "Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy" ICML 2026
[2] M. Joseph et al. "Approximate Differential Privacy of the Mechanism" ICML 2025
Critical strengths
The proposed closed-form generalized gamma mechanism (CGG) improves the efficiency of the previously established spherical generalized gamma (SGG) mechanism [1]. The authors prove that the mechanism is optimal as a function of the query dimension in the first three asymptotic terms. This is an impressive result, as it is uncommon to have optimality over more than one term, especially in differential privacy literature. The proof improves upon the previous work [1] that shows the optimality of the Gaussian mechanism for only the first asymptotic term.
[1] Y. Wei et al. "Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy" ICML 2026
Critical weaknesses
-
The MSE of the proposed CGG mechanism is worse than of the SGG mechanism (see Table 2), and is only better than the Gaussian mechanism by at most % in the low-dimension regime . The proposed algorithm is faster than SGG, however, the reported 5s for the SGG does not look too impractical either. The implementation, computational resources were not reported, preventing from making a conclusion that SGG could not be made much faster.
-
The major contribution of the paper is purely theoretical, however, in my opinion, the authors have failed to communicate the theoretical developments required for the proofs properly. In particular, the section for "converse bounds" only states the theorem and provides a long list of technical steps as a proof sketch, without any emphasis on difficulty, originality or any intuition for it whatsoever. The proposed CGG algorithm closely resembles SGG algorithm, however, the comparison with the original construction is not discussed.
-
It is unclear how realistic the assumptions 1,2 are and whether they would hold in practical scenarios of interest. According to Figure 2 the value of should be relatively small for them to hold.
-
The authors have not established a privacy composition of CGG similar to Proposition 4.2 of [1] for SGG, only saying that it would require an additional theorem.
-
The setting is limited to the approximate DP, it is unclear if one considers Renyi, zero-concentrated or Gaussian DP that the same optimality conclusion would hold. The paper considers only additive mechanisms scaled with sensitivity, without discussing much if other mechanisms could achieve even lower MSE.
[1] Y. Wei et al. "Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy" ICML 2026
Questions for authors
-
Could you clarify the intuition / major techniques required for the lower bound proof?
-
How limiting are the assumptions 1,2 ?
-
How different is CGG from SGG, are those the same mechanisms with a different way to calibrate parameters? Why does SGG have better MSE values in Table 2? Could you clarify how the time was measured and on what hardware? Why is the time decreasing as the size of the dimension grows? Only high privacy regime was evaluated, how would the mechanisms compare for larger values of epsilon? Also and are barely different privacy values, for better understanding it is important to consider a broader range of privacy parameters.
-
Would the optimality conclusions be different if Renyi-DP, zero-concentrated DP or Gaussian DP would be considered? In case it is hard to answer this theoretically, could it be evaluated numerically?
22 comments
Response to Weakness 1 of Reviewer X8Ur (W1(b))
Thank you for pointing this out. The implementation is described in Section 4.2 and Appendix H.2, and the code is in the supplementary material, where \texttt{table_mechanisms_runtime.py} reproduces Table 2. All four mechanisms are calibrated by the same routine, which solves one scalar equation for the noise scale with a one-dimensional quadrature (Appendix E.2). CGG calls this routine once. For SGG we search the box , of Wei et al. (2026) with a grid followed by a bounded simplex refinement, which calls the routine to times per setting. The refinement is needed because resolving the difference between SGG and CGG requires the minimizer to preserve at least five decimals.
The experiments ran on a desktop with an Intel Core Ultra 7 265F CPU (20 cores) and 16 GB of memory under Windows 11, in Python 3.13 with NumPy 2.3.5 and SciPy 1.16.3, as a single process without a GPU. The time ratio of to in Table~2 does not depend on the hardware. One calibration costs about 10 milliseconds for CGG and for every candidate shape of SGG at every , so the ratio is essentially the number of candidate shapes that the search evaluates.
We would like to mention that SGG can also be speed-up. Since space is limited in the main text, we present one such method in Table 7: initializing the search at the shape parameters obtained by CGG, without the grid, reduces the search from -- calibrations (- seconds) to - calibrations (-- seconds) per setting. This approach returns the same minima at eleven of the twelve settings. At it finds a minimum below CGG, where the grid search stopped at the boundary and reported a minimum below CGG. It still costs to times the CGG setup, because each search has to evaluate many candidate shapes. The fastest SGG search we found uses the CGG shape as its initialization, so the two mechanisms complement each other.
In the revised manuscript, we will add the computational resources to Section 4 and the implementation details to Appendix H.2.
Response to Weakness 2 of Reviewer X8Ur (W2(a) Part 1)
Thank you for this comment. We agree that the proof sketch of Theorem~2 lists the steps without explaining the idea behind them. Below we give the overall strategy, a table that separates known steps from new ones, and the intuition for the key step.
The six steps of Theorem 2 follow a common strategy for deriving lower bounds through optimization duality. We illustrate this strategy using a generic constrained optimization problem. In general, to solve a constrained optimization problem (primal), e.g., \begin{equation*} \begin{aligned} & y^\star= \min_{x\in\mathcal X} f(x)\ \text{subject to } g_i(x)\le0,\ i=1,\ldots,m, \end{aligned} \end{equation*} the duality strategy has four stages. (i) Form the Lagrangian dual function and invoke weak duality, i.e., every gives a lower bound . (ii) Start from a guess of the primal optimal solution , and use the complementary slackness conditions () to choose . (iii) Verify dual feasibility, ensuring that the resulting bound holds over the entire primal domain. (iv) Optimize any remaining parameters to raise . In (1), the primal variable is the noise distribution and there is one constraint for every shift with , so becomes a weight function over shifts (the threshold of Lemma 5), otherwise stages (i)--(iv) apply verbatim and lead to the six steps. For better illustration, the table below identifies the correspondence between the stages and the steps to prove Theorem 2. The table also distinguishes established steps from our new contributions and summarizes the outcome of each step.
| Stage of the dual strategy | Step | New contributions? | Outcome |
|---|---|---|---|
| (i). Invoke weak duality | 1 | No. The procedure of single-event relaxation follows Wei et al. (2026). | Establish that any with for all gives . |
| (ii). Choose dual parameters via complementary slackness | 2 | No. Restates the first-order result of Wei et al. (2026). | Gaussian threshold and the tangent of the Gaussian privacy profile at ; the limiting certificate recovers the first-order optimality of Gaussian noise. |
| (ii). Choose dual parameters via complementary slackness | 3 | Yes. Constructs an analytic threshold with on a whole interval around and , and shows that the two thresholds differ in slope at : (Lemma 7). This is the step that reaches the constant order; a point contact loses because fluctuates at scale . | Threshold whose limiting mass equals the tangent on an interval around . |
| (iii). Verify dual feasibility | 4 | Yes. Extends the sphere-coordinate normal approximation of (Diaconis & Freedman 1987) to second order, uniformly in . | Expansion of through order . |
| (iii). Verify dual feasibility | 5 | Yes. Glues near to elsewhere, adds corrections , and chooses , and so that the coefficient is affine in and cancels against , while the margin of Step 2 controls away from (Lemma 9). | Dual inequality verified for all , with lower bound ; produces , which vanishes only at the Gaussian shape . |
| (iv). Optimize the remaining parameters | 6 | Yes. Identifies the one parameter left free in Step 5, the value of at , computes the explicit coefficient of the certificate as a concave quadratic in , and maximizes it (Appendix D.5). | Maximum equals , the same number as the smallest coefficient that generalized gamma noise with attains over (eq. (15)); this matching is what makes the converse and achievability bounds agree through order . |
Response to Weakness 1 of Reviewer X8Ur (W1(a))
Thank you for your detailed review and for recognizing the significance of establishing optimality through the first three asymptotic terms, as well as the computational efficiency of CGG. We appreciate your detailed comments and questions, which greatly help us identify where clearer explanations and additional evidence are needed.
Response to W1(a): MSE of CGG compared with SGG and the Gaussian mechanism, and the running time of SGG.
Thank you for the comment. First, we would like to clarify that CGG provides an alternative to SGG for attaining the achievability bound, offering greater computational efficiency at the cost of slightly higher MSE than SGG; in other words, we do not claim that CGG has smaller MSE than SGG. This is because both mechanisms use generalized gamma noise with shape parameters (q,p). The SGG searches (q,p) numerically at every (ϵ,δ,M), and CGG provides (q,p) in closed form. The search domain of SGG contains the shape parameters of CGG, so CGG’s MSE is at least as large as SGG’s. The core contribution of CGG is the closed-form shape together with an optimality guarantee, and the speed is a by-product of the closed form. By Corollary 1, the MSE of CGG is within O(Δ22M−2) of the smallest MSE attainable by any additive noise, so no additive mechanism (including SGG) can improve on CGG by more than this order. Table 2 confirms this: the relative difference between CGG and SGG is at most 6.1×10−3 at M=10, 5.2×10−6 at M=102, and 5.1×10−9 at M=103. In contrast, the numerical search in SGG returns only an MSE value and cannot indicate how far it is from the optimum.
Regarding the comparison between CGG and the Gaussian mechanism, we would like to clarify that at M=10, Table 2 shows that CGG removes 36.0%, 14.1%, 39.8%, and 18.9% of the MSE of the analytic Gaussian mechanism (AGM) at the four privacy pairs, and Figure 1 shows up to 48.0% (all above the ``at most 10%'' interpreted by the reviewer). We agree that the relative gain decreases as M grows. This decay is dictated by the theory, and it is the fact that the paper aims to point out. Theorems 2 and 3 show that the smallest MSE of any additive noise is MSEMAGM−Δ22C(ϵ,δ)+O(Δ22M−1), where MSEMAGM=MΔ22v0 and the constant C(ϵ,δ) does not depend on M. Hence, every additive mechanism, including CGG and SGG, saves at most a constant over the Gaussian mechanism, and the relative saving decays as Mv0C(ϵ,δ). The gains in Table 2 are the limit of what noise design can achieve in this setting.
Regarding the running time, we agree that 5 seconds is acceptable for a single calibration. The difference matters when the calibration is repeated over many settings. For example, Figure 1 evaluates 1875 settings of (ϵ,δ,M). CGG needs one scale calibration of 6 to 13 milliseconds per setting, under one minute in total, while a search at the 4.9 to 8.8 seconds per setting of Table 2 is estimated to take several hours for SGG.
The running time in Table 2 does not depend on the dimension in a systematic way, so it does not grow with M and sometimes decreases. One scale calibration solves a scalar equation with a one-dimensional quadrature whose number of nodes is fixed, so it costs about 10 milliseconds for CGG and for each candidate shape of SGG at every M. The time of an SGG search is this cost multiplied by the number of candidate shapes that the search evaluates, and this number varies from one setting to another. For example, at (ϵ,δ)=(0.5,10−5) the search evaluates 493, 604, and 522 candidates at M=10, 102, and 103, which gives 5.3, 8.8, and 6.1 seconds.