{"id":"3166ed5d-c56a-4172-bbd4-a237b4789a65","arxiv_id":"2504.14730","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A convex optimization framework produces DP noise distributions that beat Gaussian and Laplace mechanisms with the same variance in moderate composition regimes, by minimizing Rényi DP at a tuned order.","lead":"This paper designs custom noise distributions for differential privacy by optimizing a Rényi divergence bound under a variance constraint. The optimized noise beats Gaussian and Laplace mechanisms with the same variance, especially for moderate numbers of query compositions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'optimal' label and reported epsilon gains rest on hand-chosen piecewise-constant geometric-tail hyperparameters (N, r, Delta) with no approximation or convergence bound; hyperparameter sensitivity is untested.","rationale":"The reader's verdict is CONDITIONAL, citing the restriction to a hand-chosen piecewise-constant geometric-tail family and the heuristic alpha update. My stress-test agrees that the family restriction is the most load-bearing concern, but sharpens it into a concrete falsifiable sensitivity check: if the reported epsilon is stable under doubling N and halving Delta (and moving r closer to 1), then the hand-chosen hyperparameters are not driving the claimed improvement. If it is not stable, the specific numbers in Figures 1, 4, and 5 could change, and the 'optimal' language in the title and abstract would be unsupported. This does not necessarily invalidate the weaker claim that the constructed distributions beat Gaussian and Laplace in tested settings, so the appropriate verdict remains CONDITIONAL pending this sensitivity analysis. I did not find a clear internal inconsistency in the convexity proof or the finite-dimensional reduction; the main gap is the missing approximation bound and the absence of a stated convergence criterion for Algorithm 3, both of which the proposed test directly probes.","tokens_in":20102,"tokens_out":10692,"duration_ms":100443,"concrete_test":"Reproduce the headline moderate-composition setting (e.g., Nc=10, s=1, delta=1e-6, sigma=8, as in Figure 1) and re-run Algorithm 1 with N doubled and Delta halved (keeping s/Delta integral), and with r moved from 0.9999 to 1-1e-6, while keeping all other inputs identical. Compare the Connect-the-Dots epsilon at delta=1e-6 to the reported value of 1.62. If the epsilon decreases by more than 1%, the distribution family is not saturated and the reported 'optimal' epsilon is an artifact of the chosen hyperparameters; if it stays within 1%, the family restriction is not biasing the headline claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim is that Algorithm 1 produces a noise distribution that beats Gaussian, Laplace, Staircase, and Cactus at the same variance in moderate composition regimes. For this claim to be meaningful as a statement about 'optimized' noise, the output must be insensitive to the user-chosen family hyperparameters N, r, and Delta, or at least demonstrably converged within the family. Section 3.1 asserts that the geometric-tail restriction 'does not significantly impact the optimization, provided that the interval is sufficiently large,' but gives no error bound and no guidance on how large N must be or how close r must be to 1. The numerical sections fix values like N=8000, Delta=0.01, and r=0.9999 without reporting any sensitivity analysis. If the reported epsilon at the target delta decreases materially when N is doubled or Delta is halved, then the headline numbers are artifacts of under-optimization rather than properties of the true optimizer within the family. If the result is stable, the concern is resolved. This is the load-bearing assumption because the paper's title and abstract promise 'optimal noise distributions,' while the evidence only supports 'better than baselines for one choice of hyperparameters.' The reader's weakest assumption identifies the same family restriction, though without a concrete falsification test.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a unified optimization framework for designing continuous and discrete noise distributions for differential privacy by minimizing Rényi divergence of a tunable order α under a cost (variance) constraint. The infinite-dimensional distribution search is reduced to a finite-dimensional convex problem over symmetric piecewise-constant (continuous) or PMF (discrete) distributions with geometric tails, controlled by hyperparameters N, r, and Δ. The resulting problem is solved by a preconditioned gradient descent algorithm that also updates α heuristically via a Newton step based on the moments accountant. The authors demonstrate that the method recovers the Staircase and Cactus mechanisms in the single- and large-composition limits, and report improved ε for fixed δ and σ in moderate composition regimes, with all final privacy guarantees computed using the Connect-the-Dots accountant.","tokens_in":20348,"tokens_out":7301,"duration_ms":64125,"significance":"If the reported gains are stable, the paper delivers a practical and unified recipe for noise design that outperforms the standard Gaussian and Laplace mechanisms at equal variance in moderate composition regimes, and the recovery of known optimal mechanisms in limiting regimes is a strong sanity check. The paper also ships code, evaluates with a state-of-the-art accountant, and provides a clean convexity reduction (Theorem 3.1) that is rigorous. The main caveats are that the 'optimal' label is tied to a surrogate moments-accountant objective and to a hand-chosen parametric family, and the numerical optimization lacks convergence guarantees; these issues do not invalidate the empirical comparison but do narrow the scope of the claims.","major_comments":[{"comment":"The finite-dimensional restriction to symmetric piecewise-constant distributions with geometric tails is asserted (Section 3.1: 'this tail assumption does not significantly impact the optimization, provided that the interval is sufficiently large') to closely approximate the true optimizer, but no approximation error bound or guidance on N, r, and Δ is given. The numerical sections fix values such as N=8000, Δ=0.01, r=0.9999 with no sensitivity analysis. If the reported ε at the target δ changes materially when N is doubled or Δ is halved, the headline improvements in Figures 4–5 and Table 1 are artifacts of under-optimization rather than properties of the true optimizer within the family. Please add a sensitivity study or prove an approximation bound before claiming optimality.","section":"§3.1, Definitions 3.3–3.4; §5"},{"comment":"The optimization minimizes the moments-accountant surrogate inf_α [N_c/(α−1) log g_α(p) + log(1/δ)/(α−1)] (Eq. (25)), not the true ε or the Connect-the-Dots accountant used for evaluation. Algorithm 1's output description ('Optimal distribution P* minimizing ε') is therefore overstated. Moreover, the preconditioned gradient descent on the nonsmooth objective max_t g_α(p,t) with a backtracking line search over a finite geometric step-size sequence, together with the Newton update for α (line 21), has no convergence or global-optimality guarantee. The statement in Section 4 that 'gradient descent will converge to the optimal objective value' is not justified. Please either provide a convergence analysis or rephrase to 'heuristic optimization' and add empirical evidence such as multiple restarts or a comparison with a certified convex solver for fixed α.","section":"§4, Algorithm 3; Algorithm 1"},{"comment":"The reduction of the continuous optimization to shifts t in {1,...,s/Δ} relies on piecewise linearity of g_α in t. The derivation in Appendix C is plausible, but the final closed form in Eq. (23) is dense and I could not independently verify every index; for instance, the last sum mixes p^α_{|t+j|} with r^{-j(1−α)} and the correspondence with Eq. (75) of Appendix C is not immediate. Since (23) is exactly the objective that the convex solver minimizes, please provide a cleaner step-by-step derivation, a machine-checkable verification, or a statement that the algebra has been symbolically verified, and explicitly specify how the case a=0 is handled in the sums.","section":"Theorem 3.6, Eq. (23); Appendix C"}],"minor_comments":[{"comment":"The definition of μ_ub assumes that at least one component of g_proj is positive; if all components are non-positive, μ_ub is undefined. Please specify the fallback behavior (e.g., terminate the line search or set μ_ub to a large value).","section":"Algorithm 3, line 10"},{"comment":"The Newton update for α is unconstrained and may push α below 1, which is outside the valid range for Rényi divergence. Please add a safeguard such as projecting α to [1+ε, ∞).","section":"Algorithm 3, line 21"},{"comment":"The caption says RDP noise is marked as the winner when it achieves more than a 2% improvement, but the text then says 'Even when another distribution is marked as the best, our noise still consistently outperforms the others, although by less than 2%.' This is confusing; please clarify the exact criterion for marking the winner and what is meant by 'outperforms' in the latter sentence.","section":"Figure 4 caption and surrounding text"},{"comment":"The text states that Gaussian noise consistently outperformed Laplace, Cactus, and Staircase across all tested settings, but the table only reports improvements over Gaussian. Since the paper's contribution is comparison with all baselines, please include the relative performance against the other baselines for at least one representative setting, or provide a supplementary table.","section":"Table 1 and Appendix D"},{"comment":"The notation γ' and γ'' for the Newton update refers to derivatives with respect to α, but γ_{p,N_c,δ}(α) depends on α both through the explicit denominator and through g_α(p). Please clarify whether the derivatives account for the α-dependence of g_α(p) and how the derivative is computed numerically.","section":"Eq. (25) and Algorithm 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid applied contribution to mechanism design for DP, and the code availability and use of Connect-the-Dots accounting are strengths. The central empirical claim is conditional: it currently rests on unexamined hyperparameters (N, r, Δ) and on a surrogate optimization objective with no convergence guarantee. I would be willing to reconsider a revised version that adds sensitivity analysis or approximation bounds, and that either proves convergence of Algorithm 3 or softens the 'optimal' terminology. The recovery of Staircase and Cactus is a good validation but does not by itself certify the moderate-regime gains."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the empirical claim is credible and reproducible, but the title's 'optimal' is stronger than what's shown. I'd send it to peer review with a request for a hyperparameter sensitivity analysis and softer wording.\n\nWhat's actually new: the finite-dimensional convex reduction plus joint optimization over the Rényi order is a clean way to tailor noise to a specific composition count. The recovery of Staircase and Cactus in the limiting regimes is a good consistency check. Most importantly, the final privacy curves are computed with Connect-the-Dots, not with the moments-accountant objective used during optimization, so the reported gains are not circular. The code is available. That is real evidence.\n\nThe soft spots are real but not uniform. The geometric-tail family is controlled by hand-set N, r, and Delta, and the paper asserts that the restriction 'does not significantly impact the optimization' without giving an approximation bound or any sensitivity study. The stress-test note is fair: if doubling N or halving Delta moves the reported epsilon by a material amount, then the headline numbers are partly artifacts of under-optimization. I can't resolve that from the paper. It's an open question, not a demonstrated flaw. The alpha update in Algorithm 3 is also a Newton heuristic with no convergence guarantee, so the output is not certified as the global minimizer of even the surrogate. That undercuts the word 'optimal,' not the comparison against Gaussian/Laplace at the tested settings.\n\nThe proof of Theorem 3.6 is dense and I didn't independently verify the algebra in (23). It looks plausible, and the discrete case follows the same derivation, so I wouldn't block on it. The citations to Cactus and Staircase are relevant; this is a direct extension of that line.\n\nWho this is for: researchers and practitioners who need a drop-in replacement for Gaussian or Laplace noise in moderate composition, and people working on DP mechanism design. It deserves a serious referee. I'd recommend conditional acceptance after the authors either provide a sensitivity analysis, add an approximation guarantee for the tail truncation, or honestly restate the result as 'best within the family and better than the standard baselines in tested regimes.'","headline":"A credible, reproducible empirical improvement over Gaussian/Laplace noise for moderate composition, with the 'optimal' label running ahead of the actual guarantees.","tokens_in":20907,"tokens_out":3055,"would_cite":true,"duration_ms":28292,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Noise distributions optimized for a fixed composition count and variance deliver smaller (ε, δ)-DP guarantees than Gaussian, Laplace, Staircase, or Cactus noise in the moderate composition regime.","keywords":["differential privacy","Renyi differential privacy","noise distribution optimization","moments accountant","convex optimization","preconditioned gradient descent","moderate composition regime","discrete Gaussian noise"],"falsifier":"For $s=1$, $\\sigma=8$, $N_c=10$, $\\delta=10^{-6}$, search a much finer family—a high-resolution histogram with no geometric-tail restriction and a dense grid over $\\alpha$—and evaluate every candidate with Connect-the-Dots; any distribution with variance $64$ and $\\varepsilon$ below $1.62$ would refute the paper's optimality claim.","tokens_in":19867,"feed_emoji":"🔒","tokens_out":15574,"duration_ms":123077,"temperature":0.7,"pith_summary":"This paper claims that choosing the noise distribution to match the exact number of times a query will be composed gives better differential privacy than the standard Gaussian or Laplace mechanisms at the same noise variance. The optimization minimizes Renyi differential privacy for an order $\\alpha$ that is itself tuned by the moments accountant, which lets one framework interpolate between the single-composition regime, where it recovers the Staircase distribution, and the large-composition regime, where it recovers the Cactus distribution. In the moderate regime of roughly 10 to 40 compositions, the optimized continuous and discrete distributions achieve a smaller $\\varepsilon$ at the same $\\delta$ and variance—about 8% to 12% lower mean-squared error on real datasets when the privacy budget is fixed. Real deployments such as repeated census releases or machine-learning training with a limited number of rounds sit precisely in this regime, so the improvement applies where standard mechanisms are routinely used.","feed_headline":"Tuned noise beats Gaussian and Laplace at 10–40 queries","feed_subtitle":"At the same variance, it buys a smaller privacy loss for 10–40 queries.","key_machinery":"The load-bearing object is $g_\\alpha(P_Z) = \\max_{t\\in S} \\mathbb{E}_{P_Z}\\left[\\left(P_Z/T_t P_Z\\right)^{\\alpha-1}\\right]$, the worst-case term inside the logarithm of the Renyi divergence of order $\\alpha$ over shifts $t$ within the sensitivity set $S$. Theorem 3.1 proves that $g_\\alpha(P_Z)$ is convex in the distribution and that symmetry is sufficient, so after restricting to symmetric piecewise-constant densities (or PMFs) with geometric tails—Definitions 3.3 and 3.4—the search becomes a finite-dimensional convex problem over bin probabilities $p_0,\\dots,p_N$ (Theorem 3.6). The solver is a preconditioned gradient descent with scaling matrix $M=\\mathrm{diag}(p)^{-1}$, which keeps iterates strictly inside the positive orthant and thereby avoids the infinite Renyi divergence that arises when supports shrink, and a Newton update of $\\alpha$ that follows the moments-accountant objective $\\gamma_{p,N_c,\\delta}(\\alpha)$.","core_discovery":"For a fixed sensitivity $s$, noise variance $\\sigma^2$, target $\\delta$, and composition count $N_c$, the paper constructs a symmetric, piecewise-constant density (or, for integer outputs, a symmetric probability mass function) with geometric tails that minimizes the Renyi differential privacy parameter at an order $\\alpha$ selected to track the moments-accountant optimum for $N_c$ and $\\delta$. The central discovery is that this distribution dominates Gaussian, Laplace, Staircase, and Cactus noise at the same variance in the moderate composition regime (roughly 10 to 40 compositions), with the largest gaps appearing for moderate $\\alpha$ values, and that the same framework automatically reproduces Cactus for very large $N_c$ and Staircase for a single composition. All reported $(\\varepsilon,\\delta)$ curves are evaluated with Connect-the-Dots accounting, so the comparison uses the same tight privacy accountant practitioners rely on.","pith_inferences":["A testable extension is to relax the geometric-tail restriction: comparing against a much larger $N$ and finer bin width, or a non-geometric tail, would quantify whether the family restriction loses anything in the moderate regime.","The same recipe—optimize a Renyi surrogate at a tuned $\\alpha$, then convert via the moments accountant—could be applied to other cost functions such as $\\ell^1$ cost or heterogeneous per-query costs, where symmetric variance-constrained shapes may not be optimal.","A practical consequence the paper does not develop: for machine-learning training with a moderate number of update rounds, replacing Gaussian noise with this mechanism could lower the noise multiplier at a fixed privacy budget, provided adaptive composition and subsampling behave for this noise as they do for Gaussian."],"forward_implications":["For any deployment with a known composition count in the moderate regime, the optimized mechanism gives a smaller $\\varepsilon$ than Gaussian or Laplace at the same variance, which is a privacy improvement at zero added noise.","Practitioners no longer need to choose among Staircase, Cactus, Gaussian, and Laplace: the same algorithm selects the right shape automatically as $\\alpha$ varies with $N_c$ and $\\delta$.","For integer-valued queries, the discrete version yields noise that beats discrete Gaussian and discrete Laplace noise while staying immune to floating-point attacks.","Because the optimized Renyi DP depends only on the ratio $\\sigma/s$, the same relative noise level transfers across query sensitivities.","The reported gains translate into roughly 8 to 12% lower mean-squared error on real datasets when the privacy budget is held fixed."],"supporting_citations":[{"why":"Defines Renyi differential privacy, its composition rule, and the conversion to (ε,δ)-DP that the optimization is built on.","marker":"(Mironov, 2017)"},{"why":"Supplies the moments accountant used to set the Renyi order α and to report final guarantees.","marker":"(Abadi et al., 2016)"},{"why":"Establishes the Cactus mechanism as optimal in the large-composition regime and provides the finite parameterization the paper adapts.","marker":"(Alghamdi et al., 2022)"},{"why":"Establishes the Staircase mechanism as optimal for single-composition pure DP, recovered by the framework as α tends to infinity.","marker":"(Geng et al., 2015)"},{"why":"Provides the Connect-the-Dots accountant used to validate all reported (ε,δ)-DP guarantees.","marker":"(Doroshenko et al., 2022)"},{"why":"Supplies the joint convexity of Renyi divergence used in the proof that the objective is convex and symmetry suffices.","marker":"(van Erven & Harremos, 2014)"},{"why":"Defines the discrete Gaussian distribution that serves as the discrete-case baseline.","marker":"(Canonne et al., 2020)"}],"fun_headline_variants":["Optimized noise beats Gaussian and Laplace for DP","Tuned noise cuts privacy loss in moderate composition","Same variance, better privacy: optimized noise wins","Gaussian no match for optimized DP noise at 10–40","Optimized noise: stronger DP per unit variance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes that the best noise distribution is well captured by a symmetric step-shaped density whose tails decay geometrically from a hand-chosen bin, and that a Newton shortcut finds the right Renyi order $\\alpha$; if the true optimum lives outside this family or the shortcut stalls at a local optimum, the output is only a local optimum, not the global one.","fun_headline_variants_meta":{"raw":{"variants":["Optimized noise beats Gaussian and Laplace for DP","Tuned noise cuts privacy loss in moderate composition","Same variance, better privacy: optimized noise wins","Gaussian no match for optimized DP noise at 10–40","Optimized noise: stronger DP per unit variance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000614,"raw_usage":{"total_tokens":2802,"prompt_tokens":845,"completion_tokens":1957,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":461,"completion_tokens_details":{"reasoning_tokens":1882}},"tokens_in":461,"tokens_out":1957,"duration_ms":14725,"temperature":1.0,"reasoning_tokens":1882,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:43:00.692170+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $s=1$, $\\sigma=8$, $N_c=10$, $\\delta=10^{-6}$, search a much finer family—a high-resolution histogram with no geometric-tail restriction and a dense grid over $\\alpha$—and evaluate every candidate with Connect-the-Dots; any distribution with variance $64$ and $\\varepsilon$ below $1.62$ would refute the paper's optimality claim.","supporting_citations":[{"cited_title":"R\\'enyi differential privacy","cited_arxiv_id":null,"evidence_quote":"Defines Renyi differential privacy, its composition rule, and the conversion to (ε,δ)-DP that the optimization is built on."},{"cited_title":"L., Kamath, G., and Steinke, T","cited_arxiv_id":null,"evidence_quote":"Defines the discrete Gaussian distribution that serves as the discrete-case baseline."}],"review_version":1}