{"id":"638d094f-5e92-42a7-8fdb-511e98b870db","arxiv_id":"2505.02798","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A piecewise Laplace mechanism attains pure differential privacy while scaling noise by per-dataset sensitivity, and it strictly dominates inverse sensitivity for sample-monotone functions.","lead":"This paper introduces a differentially private mechanism that draws piecewise Laplace noise scaled to the difficulty of the specific dataset, rather than to a worst-case global bound. It proves the mechanism is at least as accurate as the previous near-optimal inverse sensitivity mechanism and collapses to the standard Laplace mechanism when all datasets are equally hard.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Strict dominance over inverse sensitivity is proved only under sample-monotonicity, yet the abstract and Section 1.3 state it unconditionally; Corollary 4.1's equality len_f=l is the untested hinge, and it can fail for non-sample-monotone f.","rationale":"The paper's core construction and DP proof appear sound under the stated assumptions; rechecking Theorem 1's case analysis and the Lemma 3.1 equivalence did not reveal a fatal mathematical error. The load-bearing issue is that the instance-optimality claim is conditional, while the abstract and results sections present strict dominance unconditionally. The reader's weakest_assumption identified the same hinge: sample-monotonicity is needed for Corollary 4.1, and without it the comparison to the inverse sensitivity mechanism is unproved. This is a scope-of-claims concern rather than an internal inconsistency, and it does not undermine privacy correctness. The appropriate disposition remains conditional acceptance with mandatory revision: either prove dominance for general functions or state the sample-monotone restriction prominently in the abstract and main claims.","tokens_in":14072,"tokens_out":32437,"duration_ms":410045,"concrete_test":"Take a non-sample-monotone f, for instance f(t)=cos(t) with x=0 (or a finite-dataset analogue in which len_f decreases over an interval away from f(x)), set ε=1, and evaluate Pr[|Mplm(x)-f(x)|≤α] and Pr[|Minv(x)-f(x)|≤α] by numerical integration of the densities M.1 and M.2 over a fine grid. If there exists α with the PLM probability strictly smaller, the abstract's unconditional dominance claim is false; if this never happens across several such functions, the current proof still lacks a general argument and all optimality claims should be restricted to sample-monotone functions.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 proves dominance only for sample-monotone f, but the abstract and Section 1.3 state that in the continuous setting the piecewise Laplace mechanism strictly dominates the inverse sensitivity mechanism without this qualifier. The proof hinges on Corollary 4.1, which asserts len_f(y;x)=l(y;x) for all y; this equality is exactly what lets the inverse-sensitivity density be represented as the uniform-over-intervals analogue of Algorithm 1, so the per-interval truncated-exponential comparison goes through. For non-sample-monotone f, len_f need not equal l(y;x): len_f can decrease as y moves away from f(x) when the same output value is reachable by a different nearby dataset, while l(y;x) is monotone by construction. The two mechanisms then weight outcomes differently and the proof of Theorem 2 no longer applies. Thus the advertised instance-optimality unification is unsupported for general functions. The DP guarantee (Theorem 1) and the sampling procedure are not affected, so the gap is in the scope of the optimality claim, not in privacy correctness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a piecewise Laplace mechanism for differential privacy that adds noise with scale proportional to the length of output intervals determined by dataset-dependent upper and lower bounds of the function after a given number of individual changes. The mechanism is defined first through the exponential mechanism with a piecewise-linear quality score (Section 3.1) and then through a practical two-step sampler (Algorithm 1); Lemma 3.1 shows these two descriptions coincide. The paper proves that the mechanism is pure ε-DP (Theorem 1), reduces to the classical Laplace mechanism when all interval lengths equal the global sensitivity (Section 4.1), and, for sample-monotone functions, dominates the inverse sensitivity mechanism in the sense of being at least as likely to return an answer within any distance α of f(x) (Theorem 2). An approximate variant based on radius bounding functions is given in Section 5.","tokens_in":14272,"tokens_out":27248,"duration_ms":347581,"significance":"If the results hold in their advertised generality, the paper gives a clean and useful bridge between the Laplace mechanism and the inverse sensitivity/exponential mechanism framework, together with a concrete sampling algorithm. The privacy proof (Theorem 1) and the equivalence proof (Lemma 3.1) are carefully argued and appear sound; Algorithm 1 is explicit and implementable. The dominance result over the inverse sensitivity mechanism, which is known to be nearly instance optimal, is a genuinely attractive claim. The main weakness is that the abstract and Section 1.3 state the dominance result without the sample-monotone condition that Theorem 2 actually requires, and the proof of the key equality used for the comparison (Corollary 4.1) has a nontrivial gap concerning attainment of sup/inf. These issues are local and fixable, but they affect the central optimality claim, so the paper needs revision before publication.","major_comments":[{"comment":"The abstract and Section 1.3 claim, without qualification, that in the continuous setting the piecewise Laplace mechanism strictly dominates the inverse sensitivity mechanism. However, Theorem 2 proves this dominance only for sample-monotone functions (Definition 4.2), and the proof relies on Corollary 4.1, which equates len_f(y;x) with l(y;x). For non-sample-monotone functions this equality can fail, so the advertised unification with instance optimality is not supported in the stated generality. The dominance and instance-optimality claims should be explicitly qualified by sample-monotonicity, or the paper should prove dominance for a broader class.","section":"Abstract; Section 1.3; Section 4.2; Theorem 2"},{"comment":"The proof of Corollary 4.1 asserts that if len_f(y;x) > l(y;x), then because y is bounded by f(x;l(y;x)), 'there must exist y'' such that f(x'')=y''≥y' within distance l(y;x). This attainment of the supremum is not guaranteed without additional assumptions such as continuity on a compact convex domain or a finite data universe. If the supremum is approached but not attained, the stated contradiction does not follow directly; a limiting argument together with sample-monotonicity would be needed, and equality may fail on a measure-zero set such as endpoints of the range. Since Theorem 2 depends on this equality, the hypotheses of Theorem 2 should be strengthened or the proof should be repaired to show the needed equality holds almost everywhere, which is sufficient for the density argument.","section":"Section 4.2, Corollary 4.1"}],"minor_comments":[{"comment":"The statement and proof of Lemma 5.2 contain a typo: the second occurrence of ̃q_plm(y;x) should be ̃q_plm(y;x′), since the claim concerns neighboring datasets x and x′.","section":"Section 5.1, Lemma 5.2"},{"comment":"The parenthetical after Corollary 3.2 correctly notes that the statement should be restricted to y in [inf_x f(x), sup_x f(x)]; the formal statement should be corrected to include this restriction.","section":"Section 3.1, Corollary 3.2"},{"comment":"The sign variable is written as '1' in 'Sample interval 1·𝓁 where 1 ∈ {1,−1}', which is confusing because it clashes with the numeral 1; a symbol such as s or ± would be clearer.","section":"Algorithm 1"},{"comment":"The abstract says Laplace noise is drawn 'proportional to the local sensitivity,' while Section 3.2 correctly explains that the scale is proportional to the interval length Δ(x;𝓁), which is only a lower bound on local sensitivity. Aligning the wording with the formal definition would prevent overreading.","section":"Abstract; Section 3.2"},{"comment":"The theorem states a non-strict inequality for all α, while the text says the inequality is strict for almost all α; stating this strictness formally in Theorem 2 would make the claimed 'strict dominance' precise.","section":"Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The core privacy construction appears sound, and the overclaim in the abstract is the main obstacle to acceptance. If the authors qualify the dominance result by sample-monotonicity and repair the attainment gap in Corollary 4.1, the paper would be a solid contribution. The self-citations are used only for secondary composition facts and are not circular."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core construction is real and worth engaging with. The idea of sampling an interval with probability proportional to length times an exponential decay, then drawing from a truncated exponential with scale equal to the interval length, is new in the cited literature. It is simple, practical, and gives a genuine stochastic dominance over the inverse sensitivity mechanism when the function is sample-monotone. The DP proof in Theorem 1 is carefully argued and appears correct for the clean bounded continuous case. The memoryless/truncated-exponential observation is a neat trick, and Algorithm 1 is a concrete, implementable procedure. Credit is due for connecting this back to the exponential mechanism and for the worst-case reduction to Laplace.\n\nThe paper's central formal claim, Theorem 2, holds only for sample-monotone f, and the proof hinges on Corollary 4.1's equality len_f = l. The stress-test note is right: that equality can fail for non-sample-monotone functions, because len_f can decrease as y moves away from f(x) when the same output is reachable from a different nearby dataset. So the advertised unification with instance optimality is unsupported for general functions. This is not a flaw in the privacy guarantee or the sampling procedure, but it is a real gap between the abstract's bold statement and the body's condition. The abstract and Section 1.3 should be revised to carry the sample-monotone qualifier explicitly.\n\nThere are also edge cases that are waved off rather than resolved: zero-length intervals, unbounded ranges, and outputs outside the function range are handled by a remark about extended infinities. That is fine for a first draft, but a referee will want these cases either treated properly or clearly scoped out. The approximate variant in Section 5 is sketched plausibly but not fully analyzed; that is acceptable as a secondary contribution.\n\nThe paper does not lean on self-citation in a problematic way: the inverse sensitivity benchmark comes from Asi and Duchi, and the author's prior work appears only in secondary composition arguments. The derivation is self-contained and the comparison to external benchmarks is honest.\n\nWho is this for? Researchers in differential privacy who care about instance-optimal mechanisms and practical noise-adding schemes. They will find a clever mechanism and a clear route to improving on inverse sensitivity for monotone-ish functions. The paper deserves a serious referee: the main mechanism is novel, the DP proof is solid in its intended domain, and the dominance result is likely correct under the stated condition. With revisions to fix the claims' scope and edge cases, it could be a good contribution. I would send it to peer review, not desk reject.","headline":"A genuinely new piecewise Laplace mechanism with a sound DP proof and a real dominance result, but the advertised strict dominance over inverse sensitivity is only proved for sample-monotone functions and the abstract oversells it.","tokens_in":14776,"tokens_out":1344,"would_cite":true,"duration_ms":18322,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The piecewise Laplace mechanism adds noise at local-sensitivity scale, keeps pure differential privacy, and dominates the inverse sensitivity mechanism for sample-monotone functions.","keywords":["differential privacy","Laplace mechanism","local sensitivity","inverse sensitivity mechanism","exponential mechanism","piecewise sampling","instance optimality","truncated exponential"],"falsifier":"Choose a function that is not sample-monotone, such as a periodic function where an output far from $f(x)$ can be reached by changing fewer individuals than an output near $f(x)$, and numerically compare the accuracy curves $\\Pr[|M_{\\mathrm{plm}}(x)-f(x)|\\le\\alpha]$ and $\\Pr[|M_{\\mathrm{inv}}(x)-f(x)|\\le\\alpha]$; if any $\\alpha$ has the former below the latter, the dominance claim fails. Alternatively, search neighboring datasets $x,x'$ and an output $y$ for which $|q_{\\mathrm{plm}}(y;x)-q_{\\mathrm{plm}}(y;x')|>1$, which would falsify the privacy bound of Theorem 1.","tokens_in":13853,"feed_emoji":"🔒","tokens_out":13284,"duration_ms":135021,"temperature":0.7,"pith_summary":"The paper tries to show that Laplace-style noise can be adapted to the hardness of the specific dataset, rather than only to a global worst case over all datasets. Its piecewise Laplace mechanism uses a different noise scale on each interval, set by how much one individual's data can change the function output within that interval, and the paper proves this still satisfies pure $\\varepsilon$-differential privacy. The proof goes through a quality score function with sensitivity at most one, so the mechanism is an instance of the exponential mechanism; a two-step sampling procedure makes it practical. For sample-monotone functions, the mechanism is at least as likely as the inverse sensitivity mechanism to land within any distance $\\alpha$ of the true output, and it reduces exactly to the Laplace mechanism when all local sensitivities equal the global sensitivity. If these claims hold, the standard Laplace mechanism and instance-optimal adaptive mechanisms are unified.","feed_headline":"Piecewise Laplace noise is private and beats inverse sensitivity","feed_subtitle":"Drawing noise piecewise at local-sensitivity scale yields pure differential privacy and beats the inverse sensitivity mechanism.","key_machinery":"The load-bearing object is the piecewise quality score function $q_{\\mathrm{plm}}(y;x)$: for an output $y$, it first computes $\\ell(y;x)$, the minimum number of records that must change so that the interval $[\\underline{f}(x;\\ell),\\bar{f}(x;\\ell)]$ contains $y$, charges the score $-(\\ell+1)$ at the interval endpoints, and linearly interpolates inside the interval using the interval length. Feeding this score to the exponential mechanism gives exactly the piecewise Laplace density. The equivalent sampling procedure draws an interval from the inverse-sensitivity weights and then samples a truncated exponential with scale equal to the interval's length; the memoryless property of the exponential distribution makes the total exponential decay identical across intervals, and in the worst case the interpolation matches, up to a constant shift, $-|f(x)-y|/\\Delta$, reproducing the Laplace mechanism.","core_discovery":"The central claim is that one can add Laplace noise proportional to the local sensitivity of each interval without losing pure $\\varepsilon$-differential privacy. For a function $f$ and dataset $x$, let $\\bar{f}(x;\\ell)$ and $\\underline{f}(x;\\ell)$ be the largest and smallest values $f$ can take after changing at most $\\ell$ records; these endpoints define intervals whose lengths lower-bound the local sensitivity at that distance. The paper's piecewise Laplace distribution places a truncated exponential density on each interval with scale equal to the interval length, and shows that the resulting distribution is exactly the exponential mechanism applied to a piecewise-linear quality score. Because the score's sensitivity is at most one (from Corollary 3.1 and a linear-interpolation fact), the mechanism is $\\varepsilon$-DP regardless of the function's structure. In the continuous setting, the paper proves that for sample-monotone functions this distribution dominates the inverse sensitivity mechanism pointwise in the accuracy metric, and that in the worst case of equal local sensitivities it coincides with the standard Laplace mechanism.","pith_inferences":["If the piecewise construction generalizes beyond sample-monotone functions, it could replace inverse sensitivity in settings where exact inverse sensitivity is computationally expensive, since the practical sampling only needs interval endpoints.","The linear-interpolation trick may be a general recipe: any exponential mechanism with an integer-valued quality score can be sharpened by interpolating inside each level set, improving concentration without changing the privacy bound.","The approximate variant suggests a practical design pattern: compute local sensitivity only within a small radius and fall back to a global bound beyond it, which could make instance-optimal privacy practical for large graphs and high-dimensional estimates where exact intervals are intractable.","The strict improvement over uniform interval sampling implies that for continuous ranges, replacing uniform draws with truncated exponentials at the same privacy level is a free accuracy gain, an observation that might transfer to other sampling-based private mechanisms."],"forward_implications":["For every sample-monotone function and every $\\alpha>0$, the probability that the piecewise Laplace mechanism returns an answer within $\\alpha$ of $f(x)$ is at least that of the inverse sensitivity mechanism, and strictly larger for almost all $\\alpha$.","On worst-case datasets where all marginal sensitivities equal the global sensitivity, the mechanism becomes the standard Laplace mechanism and inherits the same noise scale, with privacy loss matching Laplace up to bounded-range composition and concentrated differential privacy.","The privacy guarantee only requires interval bounds satisfying the main interval-containment corollary, so approximate or coarser bounds can be used; in particular, substituting the global sensitivity beyond distance $O(1/\\varepsilon)$ keeps privacy while limiting the computation to $O(1/\\varepsilon)$ intervals.","The construction extends to $\\mathbb{R}^d$ through $L_p$ balls and radius bounding functions, giving a sensitivity-one quality score for the approximate variant and a higher-dimensional sampling procedure for $L_1$ balls."],"supporting_citations":[{"why":"Defines the Laplace mechanism and global sensitivity, the baseline distribution the paper adapts.","marker":"[DMNS06]"},{"why":"Introduces the exponential mechanism and its quality-score privacy guarantee, which the piecewise construction invokes as Proposition 1.","marker":"[MT07]"},{"why":"Defines the inverse sensitivity mechanism, the sample-monotone function class, and the continuous uniform-interval implementation that Theorem 2 dominates.","marker":"[AD20b]"},{"why":"Supplies the approximate inverse sensitivity variant and radius bounding functions used for the approximate extension and local-sensitivity upper bounds.","marker":"[AD20a]"},{"why":"Introduces the sensitivity-smoothing construction and local sensitivity bounds that form the comparison context for the paper's improvement.","marker":"[NRS07]"},{"why":"Provides the bounded-range characterization of exponential mechanism privacy used to compare the worst-case reduction against Laplace.","marker":"[DR19]"},{"why":"Supplies the bounded-range composition analysis used to argue near-optimal composition in the worst-case reduction.","marker":"[DDR20]"},{"why":"Shows the bounded-range privacy property implies concentrated differential privacy, used for the zCDP comparison.","marker":"[CR21]"}],"fun_headline_variants":["Piecewise Laplace beats inverse sensitivity","Local-sensitivity Laplace noise, now provably pure DP","A piecewise twist makes Laplace noise both local and private","Defying assumptions: piecewise Laplace satisfies pure DP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The dominance claim over the inverse sensitivity mechanism assumes the function is sample-monotone—that outputs farther from $f(x)$ are never easier to reach by changing fewer records—and if that property fails, the comparison can break even though the privacy guarantee remains.","fun_headline_variants_meta":{"raw":{"variants":["Piecewise Laplace beats inverse sensitivity","Local-sensitivity Laplace noise, now provably pure DP","A piecewise twist makes Laplace noise both local and private","Defying assumptions: piecewise Laplace satisfies pure DP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00028,"raw_usage":{"total_tokens":1656,"prompt_tokens":938,"completion_tokens":718,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":657}},"tokens_in":554,"tokens_out":718,"duration_ms":7878,"temperature":1.0,"reasoning_tokens":657,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:42:01.792151+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Choose a function that is not sample-monotone, such as a periodic function where an output far from $f(x)$ can be reached by changing fewer individuals than an output near $f(x)$, and numerically compare the accuracy curves $\\Pr[|M_{\\mathrm{plm}}(x)-f(x)|\\le\\alpha]$ and $\\Pr[|M_{\\mathrm{inv}}(x)-f(x)|\\le\\alpha]$; if any $\\alpha$ has the former below the latter, the dominance claim fails. Alternatively, search neighboring datasets $x,x'$ and an output $y$ for which $|q_{\\mathrm{plm}}(y;x)-q_{\\mathrm{plm}}(y;x')|>1$, which would falsify the privacy bound of Theorem 1.","supporting_citations":[],"review_version":1}