acceptodds
Under review as a conference paper at ICLR 2027

Converse and Achievability Bounds on the Error of Approximate Differential Privacy

Abstract

Considerable effort has been devoted to designing additive noise mechanisms that achieve -differential privacy for queries with sensitivity while minimizing the resulting error. Let denote the infimum of the mean squared error (MSE) over all -dimensional additive noise distributions that are -differentially private for every such query. We establish converse and achievability bounds on this optimal MSE. The converse (impossibility) shows that no feasible additive noise can achieve an MSE below by more than , while under a further condition on the noise shape, the achievability (possibility) shows that generalized gamma noise achieves an MSE of at most , where equation* aligned A_M(\Delta_2)=M\Delta_2^2v_0-\Delta_2^2C(\epsilon,\delta)+\Delta_2^2J(\epsilon,\delta)M. aligned equation* Here, is the exactly calibrated Gaussian variance per coordinate, and and are explicit functions of the privacy parameters alone. We derive the converse through the duality of error minimization under privacy constraints. To establish achievability, we develop an efficient noise calibration procedure that attains this upper bound. Our procedure determines the two shape parameters of the generalized gamma noise in closed form, avoiding the numerical shape search used by existing approaches. Relaxing the mild assumption on shape parameters required by our construction leaves the converse unchanged and increases the achievable upper bound by only . Numerical evaluations support the theoretical results.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential Privacy, Converse Bound and Achievability Bound

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_X8UrOpenReview ↗
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 ℓ2\ell_2 sensitivity satisfies approximate differential privacy (ε,δ)(\varepsilon, \delta)-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 ℓ2\ell_2 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 ℓ2\ell_2 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 MM 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
  1. 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 1010% in the low-dimension regime M=10M= 10. 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.

  2. 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.

  3. 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 ε\varepsilon should be relatively small for them to hold.

  4. 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.

  5. 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 ℓ2\ell_2 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
  1. Could you clarify the intuition / major techniques required for the lower bound proof?

  2. How limiting are the assumptions 1,2 ?

  3. 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 0.50.5 and 11 are barely different privacy values, for better understanding it is important to consider a broader range of privacy parameters.

  4. 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
AuthorsOpenReview ↗

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.\textbf{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)(q,p). The SGG searches (q,p)(q,p) numerically at every (ϵ,δ,M)(\epsilon,\delta, M), and CGG provides (q,p)(q,p) in closed form\textbf{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)\mathcal{O}(\Delta_2^2M^{-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−36.1\times10^{-3} at M=10M=10, 5.2×10−65.2\times10^{-6} at M=102M=10^2, and 5.1×10−95.1\times10^{-9} at M=103M=10^3. 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=10M=10, Table 2 shows that CGG removes 36.0%36.0\%, 14.1%14.1\%, 39.8%39.8\%, and 18.9%18.9\% of the MSE of the analytic Gaussian mechanism (AGM) at the four privacy pairs, and Figure 1 shows up to 48.0%48.0\% (all above the ``at most 10%10\%'' interpreted by the reviewer). We agree that the relative gain decreases as MM 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)\mathrm{MSE}^{\mathrm{AGM}}_M-\Delta_2^2C(\epsilon,\delta)+\mathcal{O}(\Delta_2^2M^{-1}), where MSEMAGM=MΔ22v0\mathrm{MSE}^{\mathrm{AGM}}_M=M\Delta_2^2v_0 and the constant C(ϵ,δ)C(\epsilon,\delta) does not depend on MM. Hence, every additive mechanism, including CGG and SGG, saves at most a constant over the Gaussian mechanism, and the relative saving decays as C(ϵ,δ)Mv0\frac{C(\epsilon,\delta)}{Mv_0}. 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 18751875 settings of (ϵ,δ,M)(\epsilon,\delta,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\textbf{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 MM 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 MM. 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)(\epsilon,\delta)=(0.5,10^{-5}) the search evaluates 493493, 604604, and 522522 candidates at M=10M=10, 10210^2, and 10310^3, which gives 5.35.3, 8.88.8, and 6.16.1 seconds.

AuthorsOpenReview ↗

Response to Weakness 1 of Reviewer X8Ur (W1(b))

Response to W1(b): Implementation and computational resources.\textbf{Response to W1(b): Implementation and computational resources.}

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 0<qM≤10<\frac{q}{M}\le1, 1≤p≤31\le p\le3 of Wei et al. (2026) with a 20×2020\times20 grid followed by a bounded simplex refinement, which calls the routine 489489 to 604604 times per setting. The refinement is needed because resolving the O(M−2)\mathcal{O}(M^{-2}) 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 523523 to 838838 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 MM, 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 489489--604604 calibrations (4.94.9-8.88.8 seconds) to 9595-239239 calibrations (0.750.75--3.13.1 seconds) per setting. This approach returns the same minima at eleven of the twelve settings. At (ϵ,δ,M)=(0.5,10−5,102)(\epsilon,\delta,M)=(0.5,10^{-5},10^2) it finds a minimum 2.013×10−22.013\times10^{-2} below CGG, where the grid search stopped at the boundary qM=1\frac{q}{M}=1 and reported a minimum 1.599×10−21.599\times10^{-2} below CGG. It still costs 3535 to 108108 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.

AuthorsOpenReview ↗

Response to Weakness 2 of Reviewer X8Ur (W2(a) Part 1)

Response to W2(a): Difficulty, originality, and intuition of the converse proof.\textbf{Response to W2(a): Difficulty, originality, and intuition of the converse proof.}

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 q(λ)=inf⁡x∈X[f(x)+∑iλigi(x)]q(\lambda)=\inf_{x\in\mathcal X}[f(x)+\sum_i\lambda_i g_i(x)] and invoke weak duality, i.e., every λ≥0\lambda\ge0 gives a lower bound y⋆≥q(λ)y^\star\geq q(\lambda). (ii) Start from a guess of the primal optimal solution x⋆x^\star, and use the complementary slackness conditions (λigi(x⋆)=0\lambda_i g_i(x^\star)=0) to choose λ\lambda. (iii) Verify dual feasibility, ensuring that the resulting bound holds over the entire primal domain. (iv) Optimize any remaining parameters to raise q(λ)q(\lambda). In (1), the primal variable is the noise distribution PP and there is one constraint for every shift hh with ∥h∥2≤Δ2\Vert h \Vert_2 \le \Delta_2, so λ\lambda becomes a weight function over shifts (the threshold θ\theta 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 strategyStepNew contributions?Outcome
(i). Invoke weak duality1No. The procedure of single-event relaxation follows Wei et al. (2026).Establish that any (θ,λ,κ)(\theta,\lambda,\kappa) with v+λhM[θ](v)≥κv+\lambda h_M{[\theta]}(v)\ge\kappa for all v≥0v\ge0 gives VM(Δ2)≥Δ22M(κ−λδ)\mathcal{V}_M(\Delta_2)\ge\Delta_2^2M(\kappa-\lambda\delta).
(ii). Choose dual parameters via complementary slackness2No. Restates the first-order result of Wei et al. (2026).Gaussian threshold θG\theta_G and the tangent ℓ\ell of the Gaussian privacy profile g(v)g(v) at v0v_0; the limiting certificate recovers the first-order optimality of Gaussian noise.
(ii). Choose dual parameters via complementary slackness3Yes. Constructs an analytic threshold Θ\Theta with j(v,Θ(v))=ℓ(v)j(v,\Theta(v))=\ell(v) on a whole interval around v0v_0 and Θ(v0)=θG(v0)\Theta(v_0)=\theta_G(v_0), and shows that the two thresholds differ in slope at v0v_0: Θ′(v0)=θG′(v0)+ϵτ∗2\Theta'(v_0)=\theta_G'(v_0)+\frac{\epsilon\tau_*}{2} (Lemma 7). This is the step that reaches the constant order; a point contact loses O(1M)\mathcal{O}(\frac{1}{M}) because VV fluctuates at scale M−12M^{-\frac{1}{2}}.Threshold Θ\Theta whose limiting mass equals the tangent on an interval around v0v_0.
(iii). Verify dual feasibility4Yes. Extends the sphere-coordinate normal approximation of (Diaconis & Freedman 1987) to second order, uniformly in vv.Expansion of hM[θ](v)h_M{[\theta]}(v) through order M−2M^{-2}.
(iii). Verify dual feasibility5Yes. Glues Θ\Theta near v0v_0 to θG\theta_G elsewhere, adds corrections uM+bM2\frac{u}{M}+\frac{b}{M^2}, and chooses uu, bb and λM=−1g′(v0)+O(M−1)\lambda_M=-\frac{1}{g'(v_0)}+\mathcal{O}(M^{-1}) so that the 1M\frac{1}{M} coefficient is affine in vv and cancels against λM\lambda_M, while the margin of Step 2 controls vv away from v0v_0 (Lemma 9).Dual inequality v+λhM[θ](v)≥κv+\lambda h_M{[\theta]}(v)\ge\kappa verified for all v≥0v\ge0, with lower bound κ−λδ=v0−C(ϵ,δ)M+O(M−2)\kappa-\lambda\delta=v_0-\frac{C(\epsilon,\delta)}{M}+\mathcal{O}(M^{-2}); produces C(ϵ,δ)=12ϵ2v02(2−τ∗)2C(\epsilon,\delta)=\frac{1}{2}\epsilon^2v_0^2(2-\tau_*)^2, which vanishes only at the Gaussian shape τ∗=2\tau_*=2.
(iv). Optimize the remaining parameters6Yes. Identifies the one parameter left free in Step 5, the value u0u_0 of uu at v0v_0, computes the explicit M−2M^{-2} coefficient of the certificate as a concave quadratic in u0u_0, and maximizes it (Appendix D.5).Maximum equals J(ϵ,δ)J(\epsilon,\delta), the same number as the smallest 1M\frac{1}{M} coefficient that generalized gamma noise with τ∗\tau_* attains over pp (eq. (15)); this matching is what makes the converse and achievability bounds agree through order 1M\frac{1}{M}.
Reviewer_QMcQOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the minimum mean squared error achievable by data-independent additive mechanisms under (ε,δ)(\varepsilon,\delta)-differential privacy for a full ℓ2\ell_2 sensitivity ball. It establishes a converse expansion containing the leading, constant, and 1/M1/M terms, and constructs a generalized Gamma mechanism that matches this expansion up to an absolute O(Δ22M−2)O(\Delta_2^2M^{-2}) gap under two stated assumptions. The shape parameters are determined explicitly, while the scale is calibrated numerically. When the shape assumption fails, the paper provides a feasible alternative with a weaker matching guarantee.

Critical strengths
  • A substantial theoretical refinement. The matching converse and achievability results quantify the finite-dimensional advantage over the analytic Gaussian mechanism much more precisely than first-order asymptotic optimality.
  • A broadly applicable converse within the stated model. The lower bound applies to all data-independent additive noise distributions, rather than only the generalized Gamma family. The dual-certificate construction is a particularly strong aspect of the paper.
  • Constructive and carefully validated results. The explicit shape prescription avoids numerical shape optimization, and the interval-arithmetic bounds provide valuable finite-dimensional evidence beyond formal asymptotic expansions.
Critical weaknesses
  1. The strongest matching result has a nontrivial restriction on the privacy parameters.
    Assumption 2 fails, for example, at (ε,δ)=(2.5,10−5)(\varepsilon,\delta)=(2.5,10^{-5}) and (3,10−5)(3,10^{-5}). In this region, the formally selected generalized Gamma spatial density is nonmonotone, and the boundary-shift calibration argument no longer applies. The authors appropriately address this through Theorem 4, but the exact 1/M1/M coefficient remains unresolved, and the guaranteed absolute optimality gap becomes O(M−1)O(M^{-1}). Although this limitation is acknowledged, describing the shape assumption as “mild” understates its effect on the coverage of the sharpest result.

  2. The asymptotic remainder does not directly provide a usable error bound at an arbitrary finite dimension.
    The constants and dimension thresholds in Theorems 2–3 are not explicit and depend on the fixed privacy pair. This matters particularly when δ\delta is very small, since the expansion coefficients themselves grow as privacy becomes stronger. The numerical certificates partly address this limitation, but clearer guidance on when the asymptotic approximation becomes quantitatively reliable would strengthen the finite-dimensional interpretation of the results.

  3. The main numerical comparisons provide limited coverage of the most informative regimes.
    The principal tables concentrate on ε∈{0.5,1}\varepsilon\in\{0.5,1\}, comfortably inside the matching region, and dimensions starting at M=10M=10. Appendix H.5 includes an outside-window example, which is useful, but broader experiments near the shape boundary and at very small dimensions would better demonstrate the practical consequences of Assumption 2 and the residual benefit of numerical shape optimization.

Questions for authors
  1. When the selected parameters satisfy ρ∗>1\rho_*>1, is there evidence that an interior shift actually produces a larger privacy loss than the boundary shift, or is Assumption 2 currently a sufficient condition needed by the proof? Could direct verification over all shift lengths clarify this distinction?

  2. Appendix E.5 states that closing the remaining gap requires a mechanism outside the monotone-density range. Does this statement refer specifically to the generalized Gamma parameterization? The constrained optimization within this family does not appear to rule out a different radially nonincreasing density attaining the same 1/M1/M coefficient.

  3. Could the authors provide additional certified comparisons at M=2,3,5M=2,3,5 and for privacy pairs near or outside the matching window, reporting both the approximation error of the asymptotic formula and the optimality gap of the feasible mechanism? This would help distinguish the limitations of the expansion from those of the selected noise family.

9 comments
AuthorsOpenReview ↗

Response to Weakness 1 of Reviewer QMcQ

Thank you for your careful review, the support of the paper, and constructive feedback. We appreciate your comments and question, which led us to new results that we believe strengthen the paper. In the responses below we (i) state the exact range of Assumption 2 and correct our use of “mild”; (ii) give an empirical criterion, r=Mϵ2v0r=\frac{M}{\epsilon^2 v_0}, for when the asymptotic formula is quantitatively reliable, tested for δ\delta down to 10−1010^{-10}; (iii) report new certified comparisons at M∈{2,3,5,10}M\in\lbrace 2,3,5,10\rbrace near and outside the matching region; and (iv) carry out the direct verification over all shift lengths that you suggest, which finds the boundary shift to be the worst one in all 5454 settings we tested. We address your comments point by point.

$\textbf{Response to W1: The matching result is restricted by Assumption~2, and ``mild'' understates the effect of this assumption.}$

Thank you for your careful reading. Your understanding of Assumption 2 and Theorem 4 is correct, and we agree that the word “mild” should be used more precisely. As the reviewer noted, Assumption 2 fails at (ϵ,δ)=(2.5,10−5)(\epsilon,\delta)=(2.5,10^{-5}) and (3,10−5)(3,10^{-5}), where ρ∗=1.004\rho_{\ast}=1.004 and 1.0161.016, respectively. For ρ∗>1\rho_{\ast} > 1 the generalized gamma density is proportional to ∥z∥2(ρ∗−1)Me−β∥z∥2p∗\lVert z\rVert_2^{(\rho_{\ast}-1)M}e^{-\beta\lVert z\rVert_2^{p_{\ast}}}, which vanishes at the origin and is nonmonotone, so Lemma 10 no longer shows that privacy at the boundary shift Δ2e1\Delta_2 e_1 covers the whole sensitivity ball. As the reviewer correctly recognized, Theorem 4 handles this case as follows. The converse bound (Theorem 2) needs only Assumption 1 and is unchanged. On the achievability side, we replace the shape by (q,p)=(M,τ∗)(q,p)=(M,\tau_{\ast}), the member with a monotone density that keeps the effective shape τ∗\tau_{\ast}, so Lemma 10 applies again. This gives

\begin{equation*} \begin{aligned} A_M(\Delta_2)-\frac{\Delta_2^2K}{M^2}\ \le\ \mathcal{V}_M(\Delta_2)\ \le\ A_M(\Delta_2)+\frac{\Delta_2^2B_{\rm sh}}{M}+\frac{\Delta_2^2K}{M^2},\qquad B_{\mathrm{sh}}=\frac{1}{2}\epsilon^2 v_0^2(\tau_{\ast}-p_{\ast})^2. \end{aligned} \end{equation*}

What is kept is the leading term and the constant term: C(ϵ,δ)C(\epsilon,\delta) remains sharp under Assumption 1 alone. What is lost is exactly what the reviewer states: the 1M\frac{1}{M} coefficient is only located in the interval [J, J+Bsh][J,\,J+B_{\mathrm{sh}}], and the guaranteed gap between the two bounds becomes Δ22BshM+O(Δ22M−2)\frac{\Delta_2^2 B_{\mathrm{sh}}}{M}+\mathcal{O}(\Delta_2^2 M^{-2}).

Numerically, this cost is small. At δ=10−5\delta=10^{-5} the ratio BshJ\frac{B_{\rm sh}}{J} is 0.0005%0.0005\%, 0.008%0.008\%, 0.05%0.05\%, 0.27%0.27\%, and 0.70%0.70\% at ϵ=2.5\epsilon=2.5, 33, 44, 66, and 88, respectively. Hence, the undetermined part stays below 0.7%0.7\% of the 1M\frac{1}{M} coefficient for ϵ≤8\epsilon\le8. For example, at (4,10−5)(4,10^{-5}) we have Bsh=2.41×10−2B_{\rm sh}=2.41\times10^{-2} against J=48.08J=48.08, and the gap Δ22BshM\frac{\Delta_2^2B_{\rm sh}}{M} is 2.4×10−62.4\times10^{-6} at M=104M=10^4, the same order as the width of our numerical bounds there.

We agree that “mild” is appropriate for Assumption 1, which fails only for δ≥0.42\delta\ge 0.42 when ϵ≤4\epsilon\le 4, but is not accurate for Assumption 2. Our wording treated the two assumptions together and was too general. In the revised manuscript, we will keep “mild” for Assumption 1 only, in the abstract, the introduction, and Section 3. For Assumption 2, we will state its range next to its definition: it holds at every δ\delta allowed by Assumption 1 for ϵ≤1\epsilon\le 1, up to ϵ≈2.3\epsilon\approx 2.3 at δ=10−5\delta=10^{-5}, and up to ϵ≈2.5\epsilon\approx 2.5 at δ=10−3\delta=10^{-3} (Table 4 and Figure 2). We will also state in the abstract and the introduction that the converse and achievability bounds match up to O(Δ22M−2)\mathcal{O}(\Delta_2^2 M^{-2}) when Assumption 2 holds. When Assumption 2 fails, Theorem 4 applies: the converse bound is unchanged, and the achievability bound increases by O(Δ22M−1)\mathcal{O}(\Delta_2^2 M^{-1}).

AuthorsOpenReview ↗

Response to Weakness 2 of Reviewer QMcQ

Response to W2: The asymptotic remainder does not give a usable error bound at a given finite dimension.\textbf{Response to W2: The asymptotic remainder does not give a usable error bound at a given finite dimension.}

Thank you for this comment. Your understanding is correct. Theorems 2 and 3 show that the constants KcvK_{\mathrm{cv}}, McvM_{\mathrm{cv}}, KachK_{\mathrm{ach}}, and MachM_{\mathrm{ach}} exist and depend only on (ϵ,δ)(\epsilon,\delta), without giving their values, as stated in Section 6. We also agree that this matters most at small δ\delta, since C(ϵ,δ)C(\epsilon,\delta) and J(ϵ,δ)J(\epsilon,\delta) grow as δ↓0\delta\downarrow 0 (Remark 3 and Proposition 6). We cannot provide explicit constants. Below we give an empirical criterion for when the expansion is reliable.

The paper already contains some evidence, but it is scattered. Remark 3 states that the constant-order conclusion applies once MM is large compared with ϵ2v0\epsilon^2 v_0. For the four privacy pairs in Section 4, ϵ2v0\epsilon^2 v_0 is between 5.35.3 and 13.913.9, so M=10M=10 is not large enough, while M≥102M\ge 10^2 is. Appendix H.3 reports the empirical bound ∣MSEMCGG−AM(Δ2)∣≤900M2\lvert\mathrm{MSE}^{\mathrm{CGG}}_M-A_M(\Delta_2)\rvert\le\frac{900}{M^2} at Δ2=1\Delta_2=1 for 0.1≤ϵ≤10.1\le\epsilon\le 1 and δ∈{10−5,10−3}\delta\in\lbrace 10^{-5},10^{-3}\rbrace. For example, at (ϵ,δ)=(0.5,10−5)(\epsilon,\delta)=(0.5,10^{-5}) the difference between AMA_M and the exact MSE of CGG is 7.37.3, 0.0650.065, and 0.00070.0007 at M=10M=10, 10210^2, and 10310^3, respectively. This evidence was not organized into a criterion and did not cover very small δ\delta.

The criterion is the ratio r=Mϵ2v0r=\frac{M}{\epsilon^2 v_0}. This is the natural parameter of the expansion: relative to the leading term, the constant term is C(ϵ,δ)Mv0=ϵ2v0M⋅(2−τ∗)22\frac{C(\epsilon,\delta)}{M v_0}=\frac{\epsilon^2 v_0}{M}\cdot\frac{(2-\tau_{\ast})^2}{2}. To test it at small δ\delta, we computed the exact MSE of CGG for δ\delta down to 10−1010^{-10}. The table reports two errors relative to the Gaussian excess MSEMAGM−MSEMCGG\mathrm{MSE}^{\mathrm{AGM}}_M-\mathrm{MSE}^{\mathrm{CGG}}_M: the error of the three-term formula AM(Δ2)A_M(\Delta_2), that is, ∣MSEMCGG−AM(Δ2)∣MSEMAGM−MSEMCGG\frac{\lvert\mathrm{MSE}^{\mathrm{CGG}}_M-A_M(\Delta_2)\rvert}{\mathrm{MSE}^{\mathrm{AGM}}_M-\mathrm{MSE}^{\mathrm{CGG}}_M}, and the error when only the constant term C(ϵ,δ)C(\epsilon,\delta) in AM(Δ2)A_M(\Delta_2) is used. The results in the table below is reported for Δ2=1\Delta_2=1.

Error relative to the Gaussian excess
(ϵ,δ)(\epsilon,\delta)ϵ2v0\epsilon^2v_0MMr=Mϵ2v0r=\frac{M}{\epsilon^2v_0}three-term formula AM(Δ2)A_M(\Delta_2)constant term CC only
(1,10−3)(1,10^{-3})6.66.610110^11.51.51.51.5%10.510.5%
10210^215150.0170.017%0.930.93%
10310^31511510.00020.0002%0.090.09%
(1,10−5)(1,10^{-5})13.913.910110^10.70.77.07.0%2929%
10210^27.27.20.050.05%3.43.4%
10310^372720.00050.0005%0.340.34%
(1,10−8)(1,10^{-8})26.026.010110^10.40.45151%4848%
10210^23.83.80.370.37%7.17.1%
10310^338380.0040.004%0.740.74%
(1,10−10)(1,10^{-10})34.434.410110^10.30.3106106%5757%
10210^22.92.90.740.74%9.69.6%
10310^329290.0070.007%1.01.0%

The table gives the following guidance. (i) The error of the three-term formula falls roughly as 0.05r2\frac{0.05}{r^2}. It is below 1%1\% once M≥3 ϵ2v0M\ge3\,\epsilon^2v_0 and below 0.1%0.1\% once M≥10 ϵ2v0M\ge10\,\epsilon^2v_0. (ii) The scale ϵ2v0\epsilon^2v_0 grows as δ\delta decreases, from about 1414 at δ=10−5\delta=10^{-5} to about 3434 at δ=10−10\delta=10^{-10}, so the same accuracy at δ=10−10\delta=10^{-10} needs a dimension about 2.52.5 times larger. This quantifies the effect of small δ\delta that the reviewer points out. (iii) For r<1r<1, the expansion should not be used: at δ=10−10\delta=10^{-10} and M=10M=10, the error of the three-term formula is as large as the excess itself. (iv) The 1M\frac{1}{M} term matters in practice. With the constant term alone, the error is about JCM\frac{J}{CM}, still 1%1\% to 10%10\% at M=102M=10^2, and adding JM\frac{J}{M} reduces it by one to two orders of magnitude. The same pattern holds at ϵ=0.5\epsilon=0.5.

This criterion is empirical and is not a theorem. The error is measured against the exact MSE of CGG, which is the achievability side. For a given finite (ϵ,δ,M)(\epsilon,\delta,M), the usable tool is the pair of numerical converse and achievability bounds of Section 4.1: they enclose the optimal MSE VM\mathcal{V}_M wherever Assumption 1 holds, do not rely on the expansion or on the constants KK and M0M_0, and take about two minutes per setting. The two tools are therefore complementary: the closed form AMA_M when r=Mϵ2v0r=\frac{M}{\epsilon^2v_0} is large, and the numerical bounds when rr is small.

In the revised manuscript, we will add this criterion and the table to Section 4.

AuthorsOpenReview ↗

Response to Weakness 3 of Reviewer QMcQ

Response to W3: Numerical coverage near the shape boundary and at very small dimensions.\textbf{Response to W3: Numerical coverage near the shape boundary and at very small dimensions.}

Thank you for this suggestion. We agree that the main tables stay inside the matching region and start at M=10M=10. We ran the experiments you describe. At δ=10−5\delta=10^{-5} the boundary of Assumption 2 is near ϵ=2.3\epsilon=2.3, so we take ϵ=2\epsilon=2 and 2.252.25 inside the matching region and ϵ=2.5\epsilon=2.5 and 33 outside it, as the column “Position” indicates, with M∈{2,3,5,10}M\in\lbrace 2,3,5,10\rbrace. The table reports the exactly calibrated MSE of four mechanisms at Δ2=1\Delta_2=1, computed as in Table 2. Outside the matching region, the CGG column uses the shape (q,p)=(M,τ∗)(q,p)=(M,\tau_{\ast}) of Theorem 4. The last column gives interval-arithmetic bounds [MSE‾M,MSE‾M][\underline{\mathrm{MSE}}_M,\overline{\mathrm{MSE}}_M] on the optimal MSE VM(1)\mathcal{V}_M(1), computed as in the upper block of Table 1.

ϵ\epsilonAssumption 2PositionMMAGMℓ2\ell_2SGGCGG[MSE‾M,MSE‾M][\underline{\mathrm{MSE}}_M,\overline{\mathrm{MSE}}_M]
22holdsinside227.9511.4991.4991.770[1.227, 1.771][1.227,\,1.771]
3311.9262.9812.9813.330[2.598, 3.331][2.598,\,3.331]
5519.8767.1977.1977.527[6.686, 7.528][6.686,\,7.528]
101039.75322.10922.00622.171[21.353, 22.172][21.353,\,22.172]
2.252.25holdsinside, near boundary226.4411.1841.1841.391[0.945, 1.391][0.945,\,1.391]
339.6622.3572.3572.626[2.079, 2.626][2.079,\,2.626]
5516.1035.7025.7025.965[5.305, 5.966][5.305,\,5.966]
101032.20717.63117.55517.691[16.985, 17.692][16.985,\,17.692]
2.52.5failsoutside, near boundary225.3400.9590.9591.124[0.746, 1.125][0.746,\,1.125]
338.0101.9101.9102.127[1.699, 2.127][1.699,\,2.127]
5513.3504.6304.6304.847[4.327, 4.848][4.327,\,4.848]
101026.70014.39914.34314.457[13.782, 14.458][13.782,\,14.458]
33failsoutside223.8680.6660.6660.779[0.485, 0.780][0.485,\,0.780]
335.8011.3271.3271.478[1.150, 1.479][1.150,\,1.479]
559.6693.2283.2283.385[2.985, 3.386][2.985,\,3.386]
101019.33810.14310.11110.196[9.722, 10.197][9.722,\,10.197]

Practical consequence of Assumption 2\textit{Practical consequence of Assumption 2} Crossing the boundary has no visible effect. From ϵ=2.25\epsilon=2.25 to ϵ=2.5\epsilon=2.5, CGG reduces 78.4% and 78.9% of the MSE of AGM at M=2M=2, and 45.1% and 45.9% at M=10M=10. Its distance to the searched shape is also unchanged across the boundary, 14.9% and 14.7% at M=2M=2 and 0.77% and 0.79% at M=10M=10. The shape (M,τ∗)(M,\tau_{\ast}) of Theorem 4 therefore behaves outside the matching region as the CGG shape does inside it.

Residual benefit of numerical shape optimization.\textit{Residual benefit of numerical shape optimization.} At M=10M=10 the search improves on CGG by less than 1% in every row. At M=2M=2, 33, and 55 the search gives a further reduction of about 15%, 10%, and 4%, and it returns the corner (q,p)=(M,1)(q,p)=(M,1) of its search box, which is the ℓ2\ell_2 mechanism. This is consistent with the theory. At these dimensions, the ratio r=Mϵ2v0r=\frac{M}{\epsilon^2 v_0} of our response to W2 is between 0.110.11 and 0.310.31, below the range in which the expansion that defines the CGG shape is accurate. CGG still captures most of the gain over the Gaussian mechanism, between 62% and 80% of its MSE for M≤5M\le 5.

Bounds.\textit{Bounds.} The intervals enclose the optimal MSE for all additive noise at each setting, and their lower ends are below every mechanism in the table. They are wider than at large MM, between 0.290.29 and 0.840.84, because at M<103M < 10^3 the converse uses a finite family of events (Appendix H.4).

In the revised manuscript, we will add this table to Appendix H and refer to it in Section 4.

Reviewer_HoU8OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes converse and achievability bounds on this optimal MSE of (ϵ,δ)(\epsilon,\delta)-DP mechanisms and use numerical evaluations support the theoretical results.

Critical strengths

The paper organization is clear, I can understand that the authors are proposing converse and achievability bounds via different, potential new techniques.

Critical weaknesses

There are two main weaknesses:

  • At first, the technical contents in the paper are very hard to follow, and the motivation and ideas behind most of the technical contents are unclear. For example, at the very beginning, end of Page 1, why answering the two questions (Q1 and Q2) needs to consider the optimization problem (1), and why use the hockey-stick divergence for the objective of the paper? Also, when it comes to Page 3, Section 2.2, the authors did not explain why need to give Lemma 1. Besides those, the proofs in appendices are very hard to follow as well. Considering the main contribution of the paper are theoreric contents, the authors are expected to put more effort on letting the readers know the ideas and motivation behind each technical tools.

  • Secondly, the contribution of the techniques are also not clear. Sometimes the authors put quite a lot effort and space on introducing rather basic things, while sometimes the key steps are not emphasized enough. It seems like the converse bound is one of the most important results, and there are six steps, so which are known or partially known in literature, which are not, and which are the most nontrivial steps? I tried to read the details in appendix, but I could not. Besides this, I would also suspect the authors have used AI tools more than they claimed in the "AI USE STATEMENT". They explicitly said that they did not use AI tool for theory parts, but some of the proof steps are quite like AI-assisted. Nevertheless, this is just my personal feeling and not the main weakness. I only care if the results are clearly presented and correct.

Please refer to the next section to see some of my other questions.

Questions for authors

I do not use AI-tools to review, so it is likely I miss some of the details and have grammar mistakes since I am not a native speaker. If so, please just indicate what I miss or where I am wrong. Thank you.

Things that i'd prefer to be clarified:

  • Why start to consider Generalized gamma noise? Has this been used in related literature?
  • Why the two assumptions are considered and needed?
  • How are the 6 steps of the proof of Theorem 2 connected? Which one is the most important, nontrial and novel?
  • Is CGG mechanims entirely novel? How is it related to existing mechanisms?
  • How are the 3 steps of the proof of Theorem 3 connected? What does the authors mean by "single-shift profile"? What is a "Uniform expansion"?
  • Why in Section 4, numerical results, the authors only consider ϵ≤1\epsilon\leq 1? How about the region where ϵ\epsilon is large?
  • It is likely some of the descriptions in Section 4 are also AI generated, beyond what the authors claim. For example, the authors say "high-precision MSE values", but 5 digits are usually not considered as high-precision. The also use words like "know values" which are not common in differential privacy literature, but please correct me if I am wrong. Again, I am more than happy to use AI tools and make the papers better, the main issue is these words and details make the paper not easy to follow and verify.

I also suggest the authors to consider adding more explanation on the ideas and motivation behind technical contributions.

10 comments
AuthorsOpenReview ↗

Response to Weakness 1 of Reviewer HoU8

We thank the reviewer for his/her careful reading and for recognizing the clear organization of the paper and the potential novelty of our techniques for proving converse and achievability bounds. In particular, we are grateful to the reviewer for highlighting where we need to better explain the motivation and key ideas behind our technical contributions.

To facilitate our discussion with the reviewer, we first briefly summarize the background and motivation of this work, which we will also explain more clearly in the revised manuscript.

Minimizing the magnitude of perturbation noise under a fixed differential privacy guarantee is a longstanding research problem, e.g., (Geng & Viswanath, 2016), (Joseph et al., 2025), (Ji & Li, 2024), (Liu et al., 2026b), and (Wei et al., 2026). In particular, (Wei et al., 2026) established the asymptotic optimality of Gaussian noise: for δ\delta below a threshold (δ≤δ⋆\delta\le\delta^\star), as the dimension M→∞M\to\infty, Gaussian noise is optimal, in the sense that no additive noise has MSE smaller than the Gaussian MSE MΔ22v0M\Delta_2^2v_0 by more than o(M)o(M). This leaves open how far the minimal MSE lies below the Gaussian MSE for \textbf{finite} MM, and which noise attains the minimal MSE. Our paper investigates this more practical setting of \textbf{finite} dimension and asks: for any fixed finite MM and prescribed privacy parameters (ϵ,δ)(\epsilon,\delta), how small can the perturbation noise be, as measured by MSE? We aim to answer this central question for arbitrary noise designs. The minimal MSE answers Q1\textbf{Q1}, and the noise that attains it answers Q2\textbf{Q2}.

W1: (a) Why formulating optimization problem as (1) to answer Q1 and Q2? (b) Why Lemma 1 is needed?\textbf{W1: (a) Why formulating optimization problem as (1) to answer Q1 and Q2? (b) Why Lemma 1 is needed?}

(a) Optimization in (1) and the hockey-stick divergence.\textbf{(a) Optimization in (1) and the hockey-stick divergence.} Thanks for the question. We would like to first clarify that in (1), the hockey-stick divergence is the constraint of the optimization (not the objective), the objective is the MSE. In the revised manuscript, we will put the hockey-stick divergence and other constraints in a new line to avoid any confusion. In the literature, the hockey-stick divergence is a standard characterization of (ϵ,δ)(\epsilon,\delta)-DP, i.e., a mechanism is (ϵ,δ)(\epsilon,\delta)-DP if and only if the hockey-stick divergence DϵD_\epsilon between its outputs on every neighboring pair is at most δ\delta (Barthe & Olmedo, 2013; Sason & Verdú, 2016; Balle et al., 2018; Sommer et al., 2019; Gopi et al., 2021; Zhu et al., 2022).

In essence, (1) is formulated to find an additive noise Z∼PZ \sim P that minimizes the MSE E[∥Z∥2]\mathbb{E}[\|Z\|^2], subject to two constraints: (i) neighboring inputs differ by a shift h=f(x′)−f(x)h = f(\mathbf{x}') - f(\mathbf{x}) bounded by the ℓ2\ell_2 sensitivity ∥h∥2≤Δ2\Vert h \Vert_2 \le \Delta_2, and (ii) the resulting mechanism satisfies (ϵ,δ)(\epsilon,\delta)-DP, i.e., the induced hockey-stick divergence DϵD_\epsilon is bounded by δ\delta. Then solving (1) leads to answers to Q1 and Q2. To be more specific, denote the infimum MSE achieved by (1) as VM(Δ2)\mathcal{V}_M(\Delta_2). Then, answer to Q1 (Corollary 2) states that the error a non-Gaussian mechanism can save is MSEMAGM−VM(Δ2)\mathrm{MSE}^{\rm{AGM}}_M-\mathcal{V}_M(\Delta_2), where MSEMAGM\mathrm{MSE}^{\rm{AGM}}_M stands for the MSE of the exactly calibrated Gaussian noise in (Balle & Wang, 2018). Answering Q2 means finding such noise that achieves VM(Δ2)\mathcal{V}_M(\Delta_2). To this end, we have developed CGG (Algorithm 1), which gives a closed-form construction of non-Gaussian noise without numerical search.

In the revised manuscript, we will better elaborate the reason we formulate (1) and its connection to the answers to Q1 and Q2.

(b) Lemma 1.\textbf{(b) Lemma 1.} We need Lemma 1 in the Preliminaries section because recent works (Wei et al. 2026; Liu et al. 2026b) have shown that spherical symmetric noise is promising in reducing the MSE of noise when achieving DP. Lemma 1 is the most fundamental approach to construct such kind of noise. The polar decomposition in Lemma 1 also allow us to just focusing on the radius of noise which significantly simply our analysis.

We will better leverage the space in the paper to clearly state why Lemma 1 is needed.

AuthorsOpenReview ↗

Response to Weakness 2 of Reviewer HoU8 (Part 1)

$ \textbf{W2: Six steps to prove Theorem 2 and AI use.} $ 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 q(λ)=inf⁡x∈X[f(x)+∑iλigi(x)]q(\lambda)=\inf_{x\in\mathcal X}[f(x)+\sum_i\lambda_i g_i(x)] and invoke weak duality, i.e., every λ≥0\lambda\ge0 gives a lower bound y⋆≥q(λ)y^\star\geq q(\lambda). (ii) Start from a guess of the primal optimal solution x⋆x^\star, and use the complementary slackness conditions (λigi(x⋆)=0\lambda_i g_i(x^\star)=0) to choose λ\lambda. (iii) Verify dual feasibility, ensuring that the resulting bound holds over the entire primal domain. (iv) Optimize any remaining parameters to raise q(λ)q(\lambda). In (1), the primal variable is the noise distribution PP and there is one constraint for every shift hh with ∥h∥2≤Δ2\Vert h \Vert_2 \le \Delta_2, so λ\lambda becomes a weight function over shifts (the threshold θ\theta 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 strategyStepNew contributions?Outcome
(i). Invoke weak duality1No. The procedure of single-event relaxation follows Wei et al. (2026).Establish that any (θ,λ,κ)(\theta,\lambda,\kappa) with v+λhM[θ](v)≥κv+\lambda h_M{[\theta]}(v)\ge\kappa for all v≥0v\ge0 gives VM(Δ2)≥Δ22M(κ−λδ)\mathcal{V}_M(\Delta_2)\ge\Delta_2^2M(\kappa-\lambda\delta).
(ii). Choose dual parameters via complementary slackness2No. Restates the first-order result of Wei et al. (2026).Gaussian threshold θG\theta_G and the tangent ℓ\ell of the Gaussian privacy profile g(v)g(v) at v0v_0; the limiting certificate recovers the first-order optimality of Gaussian noise.
(ii). Choose dual parameters via complementary slackness3Yes. Constructs an analytic threshold Θ\Theta with j(v,Θ(v))=ℓ(v)j(v,\Theta(v))=\ell(v) on a whole interval around v0v_0 and Θ(v0)=θG(v0)\Theta(v_0)=\theta_G(v_0), and shows that the two thresholds differ in slope at v0v_0: Θ′(v0)=θG′(v0)+ϵτ∗2\Theta'(v_0)=\theta_G'(v_0)+\frac{\epsilon\tau_*}{2} (Lemma 7). This is the step that reaches the constant order; a point contact loses O(1M)\mathcal{O}(\frac{1}{M}) because VV fluctuates at scale M−12M^{-\frac{1}{2}}.Threshold Θ\Theta whose limiting mass equals the tangent on an interval around v0v_0.
(iii). Verify dual feasibility4Yes. Extends the sphere-coordinate normal approximation of (Diaconis & Freedman 1987) to second order, uniformly in vv.Expansion of hM[θ](v)h_M{[\theta]}(v) through order M−2M^{-2}.
(iii). Verify dual feasibility5Yes. Glues Θ\Theta near v0v_0 to θG\theta_G elsewhere, adds corrections uM+bM2\frac{u}{M}+\frac{b}{M^2}, and chooses uu, bb and λM=−1g′(v0)+O(M−1)\lambda_M=-\frac{1}{g'(v_0)}+\mathcal{O}(M^{-1}) so that the 1M\frac{1}{M} coefficient is affine in vv and cancels against λM\lambda_M, while the margin of Step 2 controls vv away from v0v_0 (Lemma 9).Dual inequality v+λhM[θ](v)≥κv+\lambda h_M{[\theta]}(v)\ge\kappa verified for all v≥0v\ge0, with lower bound κ−λδ=v0−C(ϵ,δ)M+O(M−2)\kappa-\lambda\delta=v_0-\frac{C(\epsilon,\delta)}{M}+\mathcal{O}(M^{-2}); produces C(ϵ,δ)=12ϵ2v02(2−τ∗)2C(\epsilon,\delta)=\frac{1}{2}\epsilon^2v_0^2(2-\tau_*)^2, which vanishes only at the Gaussian shape τ∗=2\tau_*=2.
(iv). Optimize the remaining parameters6Yes. Identifies the one parameter left free in Step 5, the value u0u_0 of uu at v0v_0, computes the explicit M−2M^{-2} coefficient of the certificate as a concave quadratic in u0u_0, and maximizes it (Appendix D.5).Maximum equals J(ϵ,δ)J(\epsilon,\delta), the same number as the smallest 1M\frac{1}{M} coefficient that generalized gamma noise with τ∗\tau_* attains over pp (eq. (15)); this matching is what makes the converse and achievability bounds agree through order 1M\frac{1}{M}.
AuthorsOpenReview ↗

Response to Weakness 2 of Reviewer HoU8 (Part 2)

Step 3 is what separates our contribution from the first-order argument (Wei. et al. 2026). Recall from Step 1 that the dual parameters are a threshold function θ\theta, which selects the single privacy event kept from (1), and a multiplier λ≥0\lambda \ge 0; if v+λhM[θ](v)≥κv + \lambda h_M{\left[\theta\right]}(v) \ge \kappa for all normalized energies v=∥z∥22/(MΔ22)≥0v = \Vert z \Vert_2^2 / (M\Delta_2^2) \ge 0, where hM[θ](v)h_M{\left[\theta\right]}(v) is the hockey-stick mass of that event, then E[V]≥κ−λδ\mathbb{E}[V] \ge \kappa - \lambda \delta is a lower bound on the normalized MSE. We write (θ,λ,κ)(\theta, \lambda, \kappa) for such a dual choice together with the bound it gives. In Step 2 the limiting mass of the Gaussian threshold θG(v)=12−ϵv\theta_G(v) = \frac{1}{2} - \epsilon v is the Gaussian privacy profile g(v)g(v), and the dual inequality holds because gg lies above its tangent ℓ\ell at v0v_0, the root of g(v0)=δg(v_0) = \delta. This inequality is tight only at v0v_0 and has slack of order (v−v0)2(v-v_0)^2 away from v0v_0. At finite MM, the normalized energy VV of the optimal noise fluctuates around v0v_0 at scale M−12M^{-\frac{1}{2}}, so such a dual choice (θ,λ,κ)(\theta,\lambda,\kappa) that is tight at one point loses an amount of order 1M\frac{1}{M} in its lower bound. To avoid this loss, the limiting mass of the threshold must agree with the tangent ℓ\ell on a whole interval around v0v_0, and Lemma 7 constructs the analytic threshold with this property. Step 5 is the most laborious step. It glues Θ\Theta near v0v_0 to the threshold θG\theta_G elsewhere, checks the dual inequality v+λhM[θ](v)≥κv+\lambda h_M{\left[\theta\right]}(v)\ge\kappa on four regions of vv, and produces C(ϵ,δ)C(\epsilon,\delta). Step 6 is short once Step 5 is done, and it is where the converse and the achievability sides meet: one parameter of Step 5 remains free, the 1M2\frac{1}{M^2} term of the lower bound is a concave quadratic in it, and its maximum J(ϵ,δ)J(\epsilon,\delta) equals the minimum over the power pp of the 1M\frac{1}{M} on the achievability side (eq. 15), which is why the converse and achievability bounds agree through order 1M\frac{1}{M}.

In the revised manuscript, we will add this explanation to Section 3.1 and include the above table in Appendix D to clarify the role of each step in the proof of Theorem 2. We would also like to clarify that we derived all theoretical results ourselves and used an LLM to polish their wording, including portions of the appendix. This language editing may have contributed to the impression that some proof steps were AI-assisted. We will revise the AI Use Statement to make the description explicit.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.