{"id":"45df9d7a-e74e-49ea-be41-9af333f1eeab","arxiv_id":"2412.06541","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"DAM, a disk-shaped random response mechanism, estimates 2D spatial distributions under local differential privacy with lower Wasserstein error than previous mechanisms at fine grid granularity.","lead":"The authors design a local differential privacy mechanism that randomizes each user's 2D location into a disk-shaped high-probability zone, then reconstructs the spatial distribution from the noisy reports. The mechanism outperforms prior 1D-based and Geo-I baselines on real and synthetic spatial datasets when the grid is fine.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central optimality claim rests on an unproven surrogate: the paper never shows that maximizing pairwise sliced Wasserstein distance between mechanism outputs minimizes the W2 distance between the true and estimated distributions. DAM's optimality among SAMs is therefore not established.","rationale":"Agree with the reader's weakest_assumption: the surrogate gap is the most load-bearing concern. The paper's strongest_claim is an optimality theorem for DAM, but the proof only establishes a property of a surrogate objective. The mathematical notation in Theorem V.1 is also problematic, but even a corrected derivation would leave the central link missing. The proposed test directly compares DAM with another SAM that has the same q value and thus the same surrogate value under the paper's own formula; if actual W2 differs, the surrogate is insufficient, which would invalidate the optimality claim. If the test shows DAM is empirically best among SAM shapes, the conditional concern would be largely resolved. Independent support: the LDP guarantee is simple and correct, and the experimental comparisons are reasonable, though they lack error bars and use a nonstandard privacy calibration for SEM-Geo-I. The paper is publishable with major revisions; the reader's CONDITIONAL verdict is appropriate, and this stress-test does not change it.","tokens_in":25587,"tokens_out":14432,"duration_ms":142976,"concrete_test":"Fix a 4x4 grid, b=1, epsilon=2.0. Let q0 = 1/(pi*e^epsilon + 4b + 1) be DAM's outside probability. Implement two SAM mechanisms with identical q0: DAM (W constant inside disk) and a \"tent\" SAM with W(z) = q0 * [1 + c * (1 - ||z||/b)] inside the disk, with c chosen to satisfy the integral condition in Definition 4. Generate n=10^6 i.i.d. samples from a known distribution (e.g., uniform on the grid), apply each mechanism with the paper's GridAreaResponse, then run the EM post-process from Section VI-B. Compute the empirical W2 between the true and estimated histograms over 20 independent runs. If the tent SAM achieves a significantly lower W2 than DAM, then the paper's surrogate (which depends only on q, not on W's shape) is not faithful to the PSDEP objective, and DAM's optimality claim fails. If DAM remains best across several W shapes, the concern is weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that DAM is optimal among all SAM mechanisms for PSDEP, which minimizes W2^2(D, \\tilde D). The proof chain is: (i) Theorem V.1 computes a quantity involving the sliced Wasserstein distance between the output distributions of two inputs and obtains \\Delta(1 - (\\pi b^2 + 4b + 1)q); (ii) Theorem V.2 shows q is minimized uniquely by DAM; (iii) therefore DAM maximizes the sliced Wasserstein surrogate and is optimal. The load-bearing gap is the step from (i)-(ii) to PSDEP: no theorem in the paper proves that maximizing the pairwise sliced Wasserstein between M_{v1} and M_{v2} for all pairs v1, v2 minimizes the expected W2 between the true distribution D and the estimated distribution \\tilde D after post-processing. Section V-B merely says \"According to Reference [6]\", but that reference is a 1D result and does not cover the 2D sliced surrogate, the grid discretization, or the EM post-processing used in the algorithm. Additionally, Theorem V.1 as stated (\"partial derivative of sliced Wasserstein distance ... with respect to \\theta\") is formally incorrect: the right-hand side of Equation (7) is the 1D Wasserstein distance between Radon projections for a fixed \\theta, i.e., the integrand of the sliced Wasserstein distance, not a derivative with respect to the integration variable \\theta. Correcting this notation does not fill the missing connection to W2(D, \\tilde D). The experiments compare DAM only with MDSW, SEM-Geo-I, HUEM, and DAM-NS, so they do not test optimality against other SAM shapes with the same q. Thus the central theoretical claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the problem of estimating a spatial distribution over a 2-D domain under local differential privacy, measuring utility by the squared 2-Wasserstein distance between true and estimated distributions (PSDEP, Definition 3). It introduces a general mechanism family, Spatial Area Mechanisms (SAM, Definition 4), a concrete instance HUEM (Definition 5), and a piecewise-constant mechanism DAM (Definition 8), together with a grid-based implementation, a border-shrinkage scheme, and EM post-processing. The authors claim that DAM is optimal among all SAM mechanisms, that the radius b can be chosen via mutual information, and they report experiments on real and synthetic data comparing DAM with MDSW, SEM-Geo-I, HUEM, and DAM-NS.","tokens_in":25918,"tokens_out":9163,"duration_ms":92864,"significance":"The problem is well motivated, and the paper makes several concrete advances. Theorem IV.1 correctly proves ϵ-LDP for the SAM class; the discretization section (Theorems VI.1–VI.4) provides detailed combinatorial area calculations that are non-trivial and appear internally consistent; and the experimental study covers multiple data sets and baselines, with pseudo-code that would allow reproduction. The strong claim of optimality, however, is not supported by the current proof. The paper's contribution would still be meaningful if the claims are scaled back to 'DAM maximizes a sliced-Wasserstein separation surrogate among SAM mechanisms at fixed radius' and the empirical superiority is presented as evidence rather than proof. If the missing link between the surrogate objective and the PSDEP Wasserstein error can be supplied, the result would be a substantial contribution to private spatial statistics.","major_comments":[{"comment":"The theorem as stated is formally incorrect. The quantity in Eq. (7), the integral of the absolute difference of the two projected cumulative functions over the projection domain, is the 1-Wasserstein distance between the one-dimensional Radon projections at the fixed angle θ, i.e., the integrand of the sliced Wasserstein distance in Definition 7. It is not the partial derivative of the sliced Wasserstein distance with respect to θ, since the sliced distance is an integral over θ. Moreover, the proof introduces DIFF(z) in Eq. (4) with an unspecified domain D′, and the steps leading from Eq. (6) to Eq. (7) are not fully spelled out. The authors should restate the theorem as an identity for the pointwise (in θ) projected 1-Wasserstein distance, or provide a genuine derivative calculation.","section":"Section V-B, Theorem V.1"},{"comment":"The central optimality claim is not established because the paper never proves that maximizing the pairwise sliced Wasserstein distance between the output distributions of M_{v1} and M_{v2} over all input pairs minimizes the PSDEP objective W_2^2(D, \\tilde D) after the EM post-processing of Section VI. The sentence 'According to Reference [6]' in Section V-B is not a proof, and reference [6] is a 1-D result that does not cover the 2-D sliced surrogate, the grid discretization, or the post-processing. As a result, Theorem V.2 establishes at most that DAM maximizes a surrogate objective among SAM mechanisms for fixed b and ε. This gap is load-bearing because the paper's abstract and conclusion claim optimality for PSDEP.","section":"Section V-B, optimality transfer"},{"comment":"The lower bound on q and the characterization of DAM are direct consequences of the SAM normalization and range constraints: since W ≤ e^ε q and the mass outside the disk is fixed to (4b+1)q, the condition 1 = (4b+1)q + ∫_{‖z‖≤b} W(z) dz forces q ≥ 1/(πb^2 e^ε + 4b + 1), with equality if and only if W(z) = e^ε q on the disk. The paper should present this transparently as a constrained-optimization result about the surrogate, not as an independent derivation of PSDEP optimality.","section":"Section IV and Theorem V.2"},{"comment":"The choice of b by maximizing an upper bound on mutual information (Eqs. (9)–(12)) is not connected to the PSDEP objective. The bound assumes a uniform input distribution and does not account for the grid discretization or EM post-processing; the experiments (Figure 8) show that the empirical optimal b sometimes deviates from the analytic ˇb. This is a reasonable heuristic, but the paper should describe it as such rather than as part of the optimality argument.","section":"Section V-C"}],"minor_comments":[{"comment":"The proof defines the set as {˜v | ‖˜v − v‖_1 ≤ b} but then states its area is πb^2. The area πb^2 corresponds to the L2 ball, not the L1 ball (whose area is 2b^2). Since the mechanism is defined with the L2 norm in Definition 8, this is presumably a typo and should be corrected.","section":"Theorem V.2 proof"},{"comment":"The pseudo-code is inconsistent: the noisy map is initialized as N R, but the update on line 7 increments N M(I(x)). The code should use the same variable name throughout.","section":"Algorithm 1"},{"comment":"The expression for g(b) is missing parentheses around the argument of the first logarithm; it should read log((πb^2+4b+1)/(πb^2 e^ε + 4b + 1)).","section":"Eq. (9)"},{"comment":"The LDP proof bounds the ratio Pr[SAM(v1)∈O]/Pr[SAM(v2)∈O] without discussing the case where the denominator is zero. Since W(z) ≥ q on the output domain, the denominator can only vanish when O has measure zero, in which case the inequality is trivial, but this should be stated explicitly.","section":"Theorem IV.1 proof"},{"comment":"The Local Privacy calibration used to compare DAM and SEM-Geo-I assumes a uniform prior Pr(i)=1/n and unbiased estimation. These assumptions are not satisfied by the real data sets (e.g., crime and taxi distributions are highly non-uniform), so the fairness of the comparison between DAM and SEM-Geo-I is conditioned on an idealized setup. The paper should acknowledge this limitation when interpreting Figures 9 and 13.","section":"Section VII-B, privacy comparison"}],"recommendation":"major_revision","confidential_remarks":"The reader's report and my own reading agree on the main gap: the optimality claim is not backed by a proof connecting the sliced-Wasserstein surrogate to the PSDEP objective. The paper also has a correctable formal error in Theorem V.1. I recommend major revision. If the authors can either supply the missing connection or carefully scale back the claims, the paper would be a useful contribution to private spatial distribution estimation. The comparison with SEM-Geo-I should be reviewed to ensure that the privacy calibration is not overly favorable to DAM."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the Disk Area Mechanism is a genuine contribution to LDP spatial distribution estimation, and the experimental work is credible. The theory claiming DAM is optimal among SAM mechanisms does not hold up as written.\n\nWhat's new: DAM's disk-shaped step response is a real departure from MSW's product of 1D mechanisms and SEM-Geo-I's categorical Geo-I approach. The grid shrinkage implementation is careful, with explicit area computations, and the LDP proof (Theorem IV.1) is correct. Empirically, DAM beats MDSW and HUEM across the board, and the fine-granularity advantage over SEM-Geo-I is believable.\n\nSoft spots, in order of severity:\n\n1. The optimality claim. Theorem V.2 is correct as a statement about q: for fixed b and epsilon, SAM's normalization forces q >= 1/(pi b^2 e^epsilon + 4b + 1), with equality exactly for DAM. That is a tidy observation about the SAM family. But it only shows DAM maximizes the pairwise sliced Wasserstein distance between mechanism outputs under a surrogate objective. The paper never proves that maximizing that surrogate minimizes the W2 distance between the true and estimated distributions after EM post-processing. Section V-B just cites Reference [6], which is a 1D result and does not cover the 2D sliced surrogate or the grid discretization. So the central claim 'optimal among all SAM' is unsupported.\n\n2. Theorem V.1 is mis-stated. It calls the quantity in Equation (7) a partial derivative of the sliced Wasserstein distance with respect to theta, but the proof actually computes the integral of the difference of projected CDFs over a fixed range—that is the 1D Wasserstein distance for a fixed theta, not a derivative. The conclusion might be salvageable, but as written the theorem's statement and proof do not match.\n\n3. The q lower bound is essentially the SAM normalization constraint, so the optimality is partly built into the assumptions. That is not fatal, but it makes Theorem V.2 more a characterization of the SAM family than a deep optimality result.\n\n4. Comparison methodology. The SEM-Geo-I comparison relies on a nonstandard 'local privacy' calibration, and the plots show no error bars. Given the small differences at several parameter settings, a reader cannot tell if the gaps are real. That is fixable.\n\nWho this is for: people building LDP mechanisms for spatial data will find DAM useful as a practical building block. The paper deserves a serious referee, but the theory needs rewriting: either supply a real proof of the surrogate-to-W2 step, or downgrade the claim to 'DAM is a well-motivated SAM variant that performs best in experiments.'","headline":"DAM is a real, practical mechanism with solid experiments, but the paper's central optimality claim does not survive contact with its own proof.","tokens_in":26517,"tokens_out":2367,"would_cite":true,"duration_ms":24332,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A disk-shaped reporting rule called DAM is optimal among a broad class of LDP mechanisms for estimating 2D spatial distributions, and beats prior mechanisms on fine grids.","keywords":["local differential privacy","spatial distribution estimation","Wasserstein distance","sliced Wasserstein distance","Radon transform","Disk Area Mechanism","frequency oracle","private data release"],"falsifier":"Simulate two SAM mechanisms, DAM and a non-step radial mechanism such as HUEM, on a fixed spatial distribution (for example, a two-point mixture with distant modes) with identical ε and b, and compare the true 2D Wasserstein error $W2^{2}$ between the actual histogram and the estimated histogram over many runs. If HUEM (or any other SAM) ever achieves a strictly lower expected $W2^{2}$ than DAM on such a distribution, the sliced-Wasserstein surrogate is not faithful and the optimality claim fails; the paper's own experiments already show SEM-Geo-I beating DAM in some coarse-grid and small-ε regimes, so this is a concrete, checkable boundary.","tokens_in":25348,"feed_emoji":"🗺️","tokens_out":6294,"duration_ms":57475,"temperature":0.7,"pith_summary":"The paper targets private spatial distribution estimation: many users each report a noisy location under local differential privacy, and an analyst wants the recovered density to be as close as possible to the true one in 2D Wasserstein distance. It defines a mechanism family, Spatial Area Mechanism (SAM), in which every input point is reported according to a radial probability density bounded between q and e^ε q inside a radius b. The paper's central claim is that among all SAMs, the Disk Area Mechanism (DAM)—a constant high probability e^ε q inside a disk of radius b and constant low probability q outside—is optimal, in the sense of minimizing the sliced Wasserstein surrogate objective. If correct, this gives a closed-form design for the noise distribution. Empirically, DAM always beats the Multi-dimensional Square Wave Mechanism and beats the Geo-I-based Subset Exponential Mechanism when the grid is fine enough.","feed_headline":"Disk-shaped noise rule is optimal for private spatial maps","feed_subtitle":"DAM gives a closed-form noise design and beats existing LDP mechanisms on fine grids.","key_machinery":"The central object is the Spatial Area Mechanism (SAM), a randomized reporting rule whose output density is a radial wave function W(·) taking values between q and e^ε q, equal to q outside radius b, and integrating to 1−(4b+1)q inside. DAM is the step-function instance with W = e^ε q inside the disk of radius b. The argument runs on the sliced Wasserstein distance: the Radon transform projects the 2D densities onto lines, the 1D Wasserstein distance along each direction is summed over angles, and a partial derivative with respect to the projection angle is shown to be ∆(1 − ($πb^{2}$ + 4b + 1)q), which pins the best mechanism to the smallest q and hence to DAM. A mutual-information upper bound supplies a distribution-independent way to set b.","core_discovery":"The core discovery is an optimality theorem for 2D local privacy. For any fixed privacy budget ε and high-probability radius b, every SAM must have a minimum report probability q at least 1/($πb^{2}$ e^ε + 4b + 1); the bound comes from integrating the density over a disk of area $πb^{2}$ and its boundary region of width b. The paper proves this minimum is achieved if and only if the mechanism is DAM, whose wave function is a step: p = e^ε q inside the disk and q outside. Because no closed form exists for 2D Wasserstein distance, the argument uses the Radon transform to reduce the problem to one-dimensional slices and maximizes the sliced Wasserstein distance between the output distributions of any two inputs; the derivative of that objective is shown to be proportional to (1 − ($πb^{2}$ + 4b + 1)q), making DAM the unique maximizer. The paper then gives a closed-form choice of b derived from an upper bound on mutual information, discretizes the mechanism to a grid with a shrinkage scheme for cells crossed by the disk boundary, and reports experiments where DAM achieves the lowest measured 2D Wasserstein error among the compared mechanisms.","pith_inferences":["If the sliced Wasserstein surrogate is faithful to the true 2D Wasserstein objective, DAM should also be optimal against any mechanism with radial symmetry, not just SAMs; a direct proof of the surrogate would settle this.","The disk design generalizes naturally to k dimensions: a hypersphere of radius b with probability e^ε q inside and q outside would satisfy the same integral argument, suggesting a k-dimensional counterpart of DAM.","Because the chosen b maximizes an upper bound on mutual information under a uniform prior on inputs, real-world skewed distributions might benefit from a data-dependent b; testing DAM with b tuned to the data is a natural extension.","DAM could be plugged into hierarchical decomposition schemes for private range queries, since the paper notes its mechanism can combine with HIO/HDG/AHEAD-style methods."],"forward_implications":["For any privacy budget ε and radius b, the smallest possible low-probability level in a SAM is q = 1/(πb^2 e^ε + 4b + 1), giving a closed-form noise design.","DAM always yields a lower 2D Wasserstein error than the Multi-dimensional Square Wave Mechanism (MDSW) in the reported experiments.","DAM beats SEM-Geo-I when the grid is fine enough (larger d), since the discretized disk approaches the continuous disk as cells shrink.","The mechanism can be implemented on a grid with a shrinkage rule for boundary cells, keeping the time complexity O(ng + nk) and memory O(g).","DAM can be compared fairly to Geo-I-based mechanisms using a local-privacy loss measure, not just the nominal ε."],"supporting_citations":[{"why":"Supplies the surrogate principle: the best mechanism maximizes the Wasserstein distance between output distributions of any pair of inputs, which the paper adapts to sliced Wasserstein.","marker":"[6]"},{"why":"Establishes the lack of closed-form 2D Wasserstein distance for non-Gaussian distributions, motivating the sliced Wasserstein substitution.","marker":"[14]"},{"why":"Defines the Radon transform, the tool used to project 2D densities onto lines for the sliced distance.","marker":"[15]"},{"why":"Defines sliced Wasserstein distance, the objective used in DAM's optimality proof.","marker":"[16]"},{"why":"Provides the MDSW baseline mechanism that DAM is compared against and beats.","marker":"[10]"},{"why":"Provides the SEM-Geo-I baseline mechanism under Geo-I privacy, used for comparison.","marker":"[12]"},{"why":"Defines local privacy loss, used to make DAM and SEM-Geo-I comparable in the experiments.","marker":"[17]"},{"why":"Introduces Geo-indistinguishability, the privacy notion of SEM-Geo-I and the distance-decay assumption HUEM uses.","marker":"[20]"},{"why":"Provides Sinkhorn's algorithm for approximating Wasserstein distance at large grid sizes in the experiments.","marker":"[31]"}],"fun_headline_variants":["Disk-shaped noise provably optimal for private spatial maps","Optimal disk mechanism for local differential privacy","DAM: disk noise wins on fine grids for LDP spatial data","Private spatial maps: disk noise is the optimal choice","Provably optimal disk noise for spatial differential privacy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes that maximizing the sliced Wasserstein distance between the output distributions of a mechanism for any two inputs (for fixed b and ε) yields the mechanism that minimizes the true 2D Wasserstein distance between the actual and estimated distributions; this surrogate is adopted from an earlier one-dimensional result without a formal justification here, and the final mechanism does not itself use sliced Wasserstein when run.","fun_headline_variants_meta":{"raw":{"variants":["Disk-shaped noise provably optimal for private spatial maps","Optimal disk mechanism for local differential privacy","DAM: disk noise wins on fine grids for LDP spatial data","Private spatial maps: disk noise is the optimal choice","Provably optimal disk noise for spatial differential privacy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00028,"raw_usage":{"total_tokens":1705,"prompt_tokens":1031,"completion_tokens":674,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":647,"completion_tokens_details":{"reasoning_tokens":597}},"tokens_in":647,"tokens_out":674,"duration_ms":7548,"temperature":1.0,"reasoning_tokens":597,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T19:33:12.345382+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate two SAM mechanisms, DAM and a non-step radial mechanism such as HUEM, on a fixed spatial distribution (for example, a two-point mixture with distant modes) with identical ε and b, and compare the true 2D Wasserstein error $W2^{2}$ between the actual histogram and the estimated histogram over many runs. If HUEM (or any other SAM) ever achieves a strictly lower expected $W2^{2}$ than DAM on such a distribution, the sliced-Wasserstein surrogate is not faithful and the optimality claim fails; the paper's own experiments already show SEM-Geo-I beating DAM in some coarse-grid and small-ε regimes, so this is a concrete, checkable boundary.","supporting_citations":[{"cited_title":"Estimating numerical distributions under local differential privacy,","cited_arxiv_id":null,"evidence_quote":"Supplies the surrogate principle: the best mechanism maximizes the Wasserstein distance between output distributions of any pair of inputs, which the paper adapts to sliced Wasserstein."},{"cited_title":"Statistical aspects of wasserstein distances,","cited_arxiv_id":null,"evidence_quote":"Establishes the lack of closed-form 2D Wasserstein distance for non-Gaussian distributions, motivating the sliced Wasserstein substitution."},{"cited_title":"Helgason and S","cited_arxiv_id":null,"evidence_quote":"Defines the Radon transform, the tool used to project 2D densities onto lines for the sliced distance."},{"cited_title":"Gen- eralized sliced wasserstein distances,","cited_arxiv_id":null,"evidence_quote":"Defines sliced Wasserstein distance, the objective used in DAM's optimality proof."},{"cited_title":"Answering multi- dimensional range queries under local differential privacy,","cited_arxiv_id":null,"evidence_quote":"Provides the MDSW baseline mechanism that DAM is compared against and beats."},{"cited_title":"Local private ordinal data distribution estimation,","cited_arxiv_id":null,"evidence_quote":"Provides the SEM-Geo-I baseline mechanism under Geo-I privacy, used for comparison."},{"cited_title":"Protecting location privacy: optimal strategy against localiza- tion attacks,","cited_arxiv_id":null,"evidence_quote":"Defines local privacy loss, used to make DAM and SEM-Geo-I comparable in the experiments."},{"cited_title":"Geo-indistinguishability: differential privacy for location-based sys- tems,","cited_arxiv_id":null,"evidence_quote":"Introduces Geo-indistinguishability, the privacy notion of SEM-Geo-I and the distance-decay assumption HUEM uses."},{"cited_title":"Sinkhorn distances: Lightspeed computation of optimal transport,","cited_arxiv_id":null,"evidence_quote":"Provides Sinkhorn's algorithm for approximating Wasserstein distance at large grid sizes in the experiments."}],"review_version":1}