$d_X$-Privacy for Text and the Curse of Dimensionality

Benjamin Zi Hao Zhao; Dali Kaafar; Hassan Jameel Asghar; Robin Carpentier

REVIEW 3 major objections 6 minor 1 cited by

$d_X$-Privacy for Text and the Curse of Dimensionality

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Word-by-word $d_X$-privacy outputs the original word or an unrelated one, nearly never a close synonym, because nearest-neighbor rounding in high-dimensional embeddings isolates every word; a rank-based post-processing fix restores the…

desk verdict A genuinely useful diagnosis of why word-level dX-privacy either returns the original word or a distant one, with mostly correct probability theory; the main overclaim is universality across all embedding models. read the letter →

arxiv 2411.13784 v2 pith:QPCB7JNF submitted 2024-11-21 cs.CR

Hassan Jameel Asghar , Robin Carpentier , Benjamin Zi Hao Zhao , Dali Kaafar This is my paper · ORCID

classification cs.CR MSC 68P2760E15

keywords differentialprivacymetricwordembeddingsmultidimensionalLaplacemechanismnearestneighborsearchcurseofdimensionalitynoisydotproducttextsanitization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies the standard word-by-word $d_X$-privacy mechanism for text: add multidimensional Laplace noise to a word embedding, then round to the nearest vocabulary word. It establishes that this mechanism almost never outputs semantically similar words — it returns either the original word or a far-off, unrelated one — and that this all-or-nothing behavior persists across all values of the privacy parameter $\epsilon$ and across common embedding models. The authors show that the culprit is the nearest-neighbor post-processing step, not the noise itself: in high dimensions, every word behaves like an isolated outlier because the nearest-neighbor distance dwarfs the gaps between consecutive neighbors, while the noise vector is nearly orthogonal to every embedding. They derive the distribution, moments, and tail bounds of the noise-embedding dot product, and propose a rank-based post-processing fix that makes the mechanism output close neighbors at the expected rates. If right, this means a widely deployed privacy tool has a built-in utility failure whose cause is geometric, not statistical.

What carries the argument

The load-bearing object is the noisy dot product $Z = \langle \boldsymbol{\eta}, \mathbf{w} \rangle = r\|\mathbf{w}\|\cos\theta_{\boldsymbol{\eta},\mathbf{w}}$, a product of an independent length component and angular component. The length $R$ follows the Gamma density $f_G(r) \propto r^{n-1} e^{-\epsilon r}$; the angular component $K = \cos\theta_{\boldsymbol{\eta},\mathbf{w}}$ has density $f_B(k) = \frac{1}{B((n-1)/2, 1/2)}(1-k^2)^{(n-1)/2 - 1}$ on $[-1,1]$ and is sub-Gaussian with parameter $1/\sqrt{n}$, meaning the noise vector is nearly orthogonal to every word embedding when $n$ is large. Theorems 1 and 2 convert the question 'which vocabulary word is nearest to the perturbed embedding?' into threshold inequalities on $r\cos\theta$ with respect to the vectors $\mathbf{x}-\mathbf{w}$ and $\mathbf{y}-\mathbf{x}$; the whole argument then reduces to comparing the sizes of nearest-neighbor distances with the gaps between consecutive neighbors. Because in high dimensions $\frac{1}{2}\|\mathbf{w}-\mathbf{x}_1\|$ (the threshold that lets the original word win) is large while $\frac{\|\mathbf{w}-\mathbf{x}_2\|^2 - \|\mathbf{w}-\mathbf{x}_1\|^2}{2\|\mathbf{x}_1-\mathbf{x}_2\|}$ (the threshold that lets the nearest neighbor beat the second) is small relative to the concentrated mass of $Z$, the observed all-or-nothing behavior follows.

What would settle it

Take a transformer-based contextual embedding model, pick a word with many synonyms, compute the ratio of its nearest-neighbor distance to the difference between its first and second neighbor distances, and run the word-by-word mechanism at a mid-range $\epsilon$ (for example 10) over several thousand words, counting how often the first 100 nearest neighbors are output. If close neighbors appear at a rate comparable to distant neighbors, the universal claim fails. A lighter check: verify whether $F_Z(z_{\mathbf{w},\mathbf{x}_1})$ (the probability that the original word beats its nearest neighbor) still dominates $F_Z(z_{\mathbf{x}_1,\mathbf{x}_2})$ as strongly for such a model as it does for GloVe and Word2Vec.

Watch

Extended reading notes

Core claim

The paper's central claim is that the multidimensional Laplace mechanism for word-level $d_X$-privacy has a systematic utility failure caused by the nearest-neighbor rounding that follows the noise addition, not by the noise distribution itself. In high-dimensional embedding spaces the distance from a word to its nearest neighbor is much larger than the relative difference between its two consecutive neighbors' distances; since the noise vector is nearly orthogonal to every embedding, the perturbed point is almost always closest either to the original word or to a distant word, and the narrow band of semantically related neighbors is skipped. The authors derive the noisy dot product distribution $Z = R K$, where the length $R$ follows the Gamma density $f_G(r) \propto r^{n-1} e^{-\epsilon r}$ and the angular component $K = \cos\theta_{\boldsymbol{\eta},\mathbf{w}}$ has density $f_B(k) \propto (1-k^2)^{(n-1)/2 - 1}$ on $[-1,1]$; they prove $K$ is sub-Gaussian with variance $1/n$, so the noise is increasingly orthogonal to every word vector, and that the mass of $Z$ concentrates within $O(\sqrt{n}/\epsilon)$. Theorems 1 and 2 turn nearest-neighbor selection into threshold conditions on this dot product: the original word beats a neighbor when $r\cos\theta_{\boldsymbol{\eta},\mathbf{x}-\mathbf{w}} < \frac{1}{2}\|\mathbf{w}-\mathbf{x}\|$, and a neighbor beats the next neighbor only under the analogous condition with $\|\mathbf{x}_1-\mathbf{x}_2\|$ in the denominator. The measured geometry of GloVe, Word2Vec, and fastText makes the first condition almost always true and the second almost never, which is exactly the observed pattern. A post-processing step that resamples among the ranks of the nearest neighbor, with probability proportional to $\exp(-c\epsilon\, d_{NN}(\mathbf{x}^*, \mathbf{x}))$, is shown to restore the expected exponential decay of output frequency with semantic distance.

Load-bearing premise

The universal explanation assumes that in every high-dimensional word embedding model, each word's nearest neighbor is much farther away than the gap between consecutive neighbors' distances; the paper only measures this for GloVe (two vocabularies), Word2Vec, and fastText, so if a model such as a transformer-based embedding has differently shaped local distance profiles, the mechanism could behave as expected there even though the noise analysis remains correct.

Editorial extensions

If this is right

For a fixed word vocabulary and $\epsilon$, the output distribution of the mechanism is effectively binary — original word or far-off word — so the privacy-utility tradeoff promised by $d_X$-privacy is not delivered in the word-by-word setting.
The same failure mode is predicted for any mechanism that adds Laplace-style noise in a high-dimensional space and then rounds to the nearest catalogued point, including geo-indistinguishability deployments on high-dimensional auxiliary data.
The proposed rank-based resampling fix is a post-processing step, so it inherits the original mechanism's $d_X$-privacy guarantee without modifying the noise; the only new cost is a per-vocabulary tuning constant $c$.
The concentration bound $O(\sqrt{n}/\epsilon)$ for the noisy dot product gives a practical rule of thumb: to see close neighbors appear, the privacy budget must scale with $\sqrt{n}$ unless the embedding space is restructured.
Because every word is effectively an outlier in high dimensions, the isolated-point critique of $d_X$-privacy applies universally to text embeddings, not just to rare or unusual words.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's universal phrasing ('any word embedding model') is asserted but only measured on GloVe, Word2Vec, and fastText; a transformer-based contextual embedding model with a different local distance profile would be the decisive test of the universality claim.
The open problem the authors pose — a metric that flattens nearest-neighbor gaps while satisfying the metric axioms — points to data-dependent metrics that rescale distance by local density, in the spirit of elastic distinguishability, as a promising route to a $d_X$-private mechanism that outputs neighbors at the intended rates.
A corollary the authors do not draw: because the angular component $K$ has variance $1/n$ regardless of the embedding's distribution, any high-dimensional perturbation scheme that rounds to the nearest catalogued point inherits this orthogonality failure, so the effect should appear in other domains such as high-dimensional location or sensor data.
One testable extension: instead of a full nearest-neighbor search, one could first project the noisy embedding onto the subspace spanned by the original word's $k$ nearest neighbors; if the projection restores comparable thresholds, the failure could disappear without an extra tuning constant.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this paper earns its place. It identifies why the standard word-level multidimensional Laplace mechanism for dX-privacy behaves so oddly—almost always outputting the original word or a completely dissimilar word, and almost never a semantically close neighbor—and shows the cause is the post-processing nearest-neighbor search, not the noise distribution. The new analytic results, the angular component of the noisy dot product (beta density, Var[K]=1/n), the moment formula, sub-Gaussianity, and the tail bounds, are mostly correct; Var[Z]=(n+1)/ε^2 and the probabilistic interpretation in Section 6 are clean. The empirical contrast between z_{w,x1} and z_{x1,x2} explains the bimodal output convincingly.

Credit where due: the pathology is reproduced across GloVe, Word2Vec, and fastText, the paper makes clear this is not a few isolated outliers but the norm for high-dimensional embeddings, and the code is released. The proposed fix is honest—a post-processing reranking step that does not change the privacy guarantee—and the authors explicitly flag that the temperature c is fitted per vocabulary.

Soft spots, in proportion. The abstract's 'any word embedding model' is stronger than the evidence: all tested embeddings are static, non-contextual models with similar Euclidean geometry. Transformer-based or contextual embeddings could have a different local distance profile, and the crucial inequality is an empirical input, not a consequence of the theorems. That is the main load-bearing gap, but it is fixable by testing contextual embeddings or by narrowing the claim. Smaller issues: Table 2 and Figures 2, 6, and 8 lack error bars even though the values come from sampling; Theorem 8 states c1∈R but the proof needs c1>0 for the tail bound to be meaningful; and the fix's c is a free parameter, so the utility improvement is only as robust as that per-vocabulary tuning. None of these undermine the core diagnosis.

Who this is for: anyone using word-level metric DP for text, and mechanism designers working on Mahalanobis or truncated exponential mechanisms that keep a nearest-neighbor post-processing step. It deserves a serious referee; the central claim is reproducible and the math is sound enough to build on. Send it to review.

Referee Report

3 major / 6 minor

Summary. The paper studies the word-level multidimensional Laplace mechanism for d_X-privacy applied to text. It reports and analyzes a systematic utility failure: the mechanism, after nearest-neighbor post-processing, almost always returns either the original word or a semantically distant word, and rarely returns nearby semantic neighbors. The authors derive the distribution of the dot product between the Laplace noise vector and a word embedding, showing that its angular component follows a beta distribution with variance 1/n, that it is sub-Gaussian with parameter 1/sqrt(n), and that the overall dot product is concentrated within O(sqrt(n)/epsilon). They then use this distribution to explain the bimodal behavior through inequalities involving the distance from a word to its nearest neighbor versus the relative distances between consecutive neighbors. Finally, they propose a rank-based post-processing fix with a temperature parameter c and compare it with the original mechanism and with the exponential mechanism of Yue et al.

Significance. If the central claim holds, the paper identifies a practically important and previously under-explained failure mode of a widely used d_X-privacy mechanism for text, and it contributes a clean probabilistic characterization of high-dimensional Laplace noise (the noisy dot product distribution, its moments, and tail bounds). The formal derivations in Sections 4 and 5 appear sound: the beta density, Var[K]=1/n, Var[Z]=(n+1)/epsilon^2, and the sub-Gaussian tail bound all check out, and the paper includes several machine-checkable proofs and released code. The proposed fix is simple and respects post-processing immunity. The main weakness is the gap between the universal wording of the empirical claim ('any word embedding model') and the evidence, which covers only static, non-contextual embedding families. The formal theorems apply to a fixed embedding set; the local-distance inequality that drives the explanation is an empirical premise, and that premise is not yet established for transformer-based or contextual embeddings.

major comments (3)

[Abstract, Section 1, Section 6.2, Table 2] The abstract and introduction claim that the nearest-neighbor distance of a word in 'any word embedding model' is much larger than the relative difference in distances to its consecutive neighbors, but the evidence in Table 2 and Figures 2 and 6 covers only GloVe (two vocabularies, several dimensions), Word2Vec, and fastText. These are all static, non-contextual embedding families with broadly similar training objectives and Euclidean geometry. Theorems 1--8 are proved for a fixed embedding set and do not by themselves imply the local-distance inequality; that inequality is an empirical input to the central explanation. If contextual or transformer-based embeddings have different local distance profiles, the observed bimodal behavior could be a property of the tested static embeddings rather than a universal curse of dimensionality. Since the paper uses the universal claim to motivate both the analysis and the proposed fix, this missing case is load-bearing. Please either add analogous measurements (e.g., z_{w,x1}, z_{x1,x2}, z_{x1,x101} and plots of F_Z) for one or more contextual embedding models, or explicitly qualify the claim to the class of embeddings for which the inequality has been verified.
[Section 6.2, Table 2, Figures 2, 6, 8] The empirical support for the central geometric claim lacks error reporting. The quantities z_{w,x1}, z_{x1,x2}, and z_{x1,x101} in Table 2 are averages over 5,000 randomly sampled words, but no standard errors, confidence intervals, or per-word distributions are reported. The same is true for the proportions in Figures 2, 6, and 8. Because the entire explanation rests on the gap between z_{w,x1} and z_{x1,x2}, the reader cannot tell whether this gap is systematic across words or driven by a minority of outliers. In addition, for the proposed fix in Section 7, the temperature c is selected per vocabulary by 'trying different values and choosing the one that gives the best result,' but the selection procedure and whether the evaluation words are independent of the selection are not specified. Please report the spread of the z quantities, add error bars or confidence bands to the proportion plots, and clarify how c is chosen for the reported fix.
[Theorem 8] The statement of Theorem 8 says 'for all c1,c2 in R, where c2 > 1,' but the proof requires c1 >= 0. Specifically, the step Pr[Z <= c1 c2 sqrt(n)/epsilon] >= Pr[K <= c1/sqrt(n)] Pr[R <= c2 n/epsilon] uses the implication K <= c1/sqrt(n) and R <= c2 n/epsilon to conclude R K <= c1 c2 sqrt(n)/epsilon, which is valid only when c1 is nonnegative. The proof also appears to use the decomposition (c1/sqrt(n))(c2 n/epsilon), which should be stated explicitly rather than left implicit in the displayed equation. Please correct the domain of c1 and the displayed algebra.

minor comments (6)

[Theorem 2] The statement of Theorem 2 has 'cos theta_{w-x, y+x}' in the first term, while the proof and Eq. (22) use 'cos theta_{w-x, y-x}'. The statement should be corrected to y - x.
[Theorem 6 proof] The last displayed equality of the proof of Theorem 6 writes 'e^{-sigma^2 lambda^2/2}'; the exponent should be positive, e^{+sigma^2 lambda^2/2}, to match the definition of a sub-Gaussian bound.
[Theorem 1 proof] The proof of Theorem 1 says 'in the second last step, we have used Theorem 3' for the elementary identity <x,y> = ||x|| ||y|| cos theta. That identity is not Theorem 3; it should be referenced to the displayed 'elementary fact' in Section 3 or renumbered.
[Figure 2 caption] The caption of Figure 2 identifies the right panel as 'Word2Vec,' while the text immediately above the figure says the pattern is shown for 'the GloVe-Wiki and fastText embedding models.' Please make the caption consistent with the text and with Figure 8.
[Section 7] The comparison of the proposed fix with the exponential mechanism of Yue et al. is illustrative but not quantitative. It would strengthen the paper to report a utility metric (e.g., average semantic similarity of outputs to the original word, or downstream task accuracy) in addition to the proportion curves.
[Throughout] There are several typographical errors, including 'santize'/'santized' in Sections 1 and 8, 'Glove' in Figure 2, and 'c+2' in the paragraph after Theorem 8. These should be corrected in revision.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the paper's formal derivation is self-contained, and its key empirical claims are measured inputs or explicitly fitted parameters rather than consequences of the conclusions.

full rationale

The core analysis is self-contained. The noisy dot product distribution, its moments, sub-Gaussian property, and tail bounds (Theorems 3, 4, 6, 8, 9) follow from the definition of the multidimensional Laplace mechanism and standard probability theory, without assuming the paper's main conclusion. The observed bimodal behavior is demonstrated empirically in Figures 1-2 and Table 2, not derived from the paper's own claims. The explanation in Section 6 uses the measured inequality z_w,x1 >> z_x1,x2 as an empirical premise; the theorems are conditional on embedding geometry and do not presuppose the outcome. The proposed fix in Section 7 uses a temperature constant c that is explicitly chosen per vocabulary and labeled as empirically determined, so no fitted parameter is presented as a prediction. The self-citation [8] reports the initial observation, but the current paper independently reproduces it in Figure 2, making the earlier work non-load-bearing. The main concern is the abstract's universality claim ('any word embedding model') being supported only by GloVe, Word2Vec, and fastText; this is a scope or correctness issue, not a circularity issue. Overall, the derivation chain is not forced by its own inputs, so the circularity score is low.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central derivation is self-contained once the gamma noise model is accepted. The main concessions are the noise-length distribution inherited from prior dX-privacy work, the domain assumption that Euclidean distance reflects semantics, and the empirical generalization that all high-dimensional word embeddings exhibit the nearest-neighbor gap. The fix introduces a tuned constant c, which is a free parameter.

free parameters (2)

c (fix temperature) = c=0.04 (GloVe-Wiki 300d), c=0.007 (Word2Vec 300d)
Chosen by trying different values until the output proportions of original, close, and distant neighbors looked acceptable; the value is vocabulary-specific.
close-neighbor threshold (k=100) = 100
Defines which outputs count as 'close' in the empirical plots; chosen for visualization and not part of the mechanism.

assumptions (3)

standard math The length of the multidimensional Laplace noise vector follows a Gamma(shape=n, rate=epsilon) distribution.
Inherited from the standard dX-privacy sampling procedure and derived in Appendix B; the paper builds on this without re-deriving it as a new result.
domain assumption Euclidean distance in word embedding space is a meaningful proxy for semantic similarity.
The paper relies on this (Section 3.1) for the nearest neighbor post-processing to be a sensible utility operation; plausible for the tested models but not universally proven.
domain assumption The nearest-neighbor gap property holds across word embedding models.
Abstract states the phenomenon occurs 'in any word embedding model'; the paper verifies it only for GloVe, Word2Vec, and fastText, making the universality claim an assumption rather than a theorem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of $d_X$-Privacy for Text and the Curse of Dimensionality." pith.science (2026). https://pith.science/paper/QPCB7JNF

@misc{pith2026241113784,
  author       = {Pith},
  title        = {Pith review of: $d_X$-Privacy for Text and the Curse of Dimensionality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QPCB7JNF}},
  note         = {Machine review of arXiv:2411.13784}
}

abstract

A widely used method to ensure privacy of unstructured text data is the multidimensional Laplace mechanism for $d_X$-privacy, which is a relaxation of differential privacy for metric spaces. We identify an intriguing peculiarity of this mechanism. When applied on a word-by-word basis, the mechanism either outputs the original word, or completely dissimilar words, and very rarely outputs semantically similar words. We investigate this observation in detail, and tie it to the fact that the distance of the nearest neighbor of a word in any word embedding model (which are high-dimensional) is much larger than the relative difference in distances to any of its two consecutive neighbors. We also show that the dot product of the multidimensional Laplace noise vector with any word embedding plays a crucial role in designating the nearest neighbor. We derive the distribution, moments and tail bounds of this dot product. We further propose a fix as a post-processing step, which satisfactorily removes the above-mentioned issue.

Figures

Figures reproduced from arXiv: 2411.13784 by the authors.

**Figure 1.** The proportion of times the original value, its close [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 3.** An analogy of the issues of applying 𝑑X-privacy to high-dimensional word embeddings using location data. The nearest neighbor of the perturbed location of the residents of Hawaii tends to be Hawaii itself, unlike the states in mainland USA. The circles indicate the probability density of the noise vector. The map is extracted from Google Maps. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

Figures from the paper (8 more)

**Figure 4.** Figure 4: The noise distribution for 𝑛 = 2 with 10,000 sampled points. Subfigure a shows the distribution of the length of noise vector, i.e., 𝑟 through Eq. (2). Subfigure b is the unit vector produced by normalizing the 2D Gaussian N (0, 𝐼) (Eq. (1)), where 𝐼 is the identity m…

**Figure 5.** Figure 5: Illustrations of Theorems 1 and 2. Subfigure a illustrates Theorem 1, Subfigure b shows a geometric interpretation of [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

**Figure 6.** Figure 6: The probabilities 𝐹𝑍 (𝑧w,x1 ) (solid) and 𝐹𝑍 (𝑧x1,x2 ) (dashed) where 𝑧w,x1 and 𝑧x1,x2 are as given in [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]

**Figure 7.** Figure 7: Example used to illustrate the fact that [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]

**Figure 8.** Figure 8: The proportion of times the original word, its close [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]

**Figure 9.** Figure 9: The proportion of times the original word, its close [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]

**Figure 10.** Figure 10: Since the point needs to have a uniform distribution, we have that 𝑓𝑅 (𝑟) ∝ 2𝜋𝑟. To make it into a probability density function, we 17 [PITH_FULL_IMAGE:figures/full_fig_p017_10.png]

**Figure 10.** Figure 10: Sampling a point uniformly at random on and [PITH_FULL_IMAGE:figures/full_fig_p018_10.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Preempting Text Sanitization Utility in Resource-Constrained Privacy-Preserving LLM Interactions
cs.CR 2024-11 conditional novelty 6.0 of 10

A local small language model can predict when a differentially private sanitized prompt will still yield useful LLM output, saving up to 20% of wasted API calls, and an exact-nearest-neighbor implementation of the dX-...

Reference graph

Works this paper leans on

42 extracted references · 33 canonical work pages · cited by 1 Pith paper

[1]

2001.Understanding analysis

Stephen Abbott et al. 2001.Understanding analysis. Vol. 2. Springer

work page 2001
[2]

Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. 2001. On the surprising behavior of distance metrics in high dimensional space. InDatabase theory—ICDT 2001: 8th international conference London, UK, January 4–6, 2001 proceedings 8. Springer, 420–434

work page 2001
[3]

Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catus- cia Palamidessi. 2013. Geo-indistinguishability: Differential privacy for location- based systems. InProceedings of the 2013 ACM SIGSAC conference on Computer & 13 Proceedings on Privacy Enhancing Technologies YYYY(X) Hassan Jameel Asghar, Robin Carpentier, Benjamin Zi Hao Zhao...

work page 2013
[4]

Andreas Athanasiou, Konstantinos Chatzikokolakis, and Catuscia Palamidessi

work page
[5]

nearest neighbor

Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When is “nearest neighbor” meaningful?. InDatabase Theory—ICDT’99: 7th International Conference Jerusalem, Israel, January 10–12, 1999 Proceedings 7. Springer, 217–235

work page 1999
[6]

Sayan Biswas and Catuscia Palamidessi. 2023. PRIVIC: A privacy-preserving method for incremental collection of location data.Proceedings on Privacy En- hancing Technologies2024, 1 (2023), 582–596

work page 2023
[7]

2020.Foundations of data science

Avrim Blum, John Hopcroft, and Ravindran Kannan. 2020.Foundations of data science. Cambridge University Press

work page 2020
[8]

Robin Carpentier, Benjamin Zi Hao Zhao, Hassan Jameel Asghar, and Dali Kaafar

work page

Show all 42 references

[9]

Ricardo Silva Carvalho, Theodore Vasiloudis, Oluwaseyi Feyisetan, and Ke Wang
[10]

2024.Statistical inference

George Casella and Roger Berger. 2024.Statistical inference. CRC Press

2024
[11]

Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. 2013. Broadening the scope of differential privacy using metrics. InPrivacy Enhancing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 201...

2013
[12]

Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Marco Stronati. 2015. Constructing elastic distinguishability metrics for location privacy.Proceedings on Privacy Enhancing Technologies(2015)

2015
[13]

Robert J Durrant and Ata Kabán. 2009. When is ‘nearest neighbour’meaningful: A converse theorem and implications.Journal of Complexity25, 4 (2009), 385–397

2009
[14]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Cali- brating noise to sensitivity in private data analysis. InTheory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. Springer, 265–284

2006
[15]

Natasha Fernandes, Mark Dras, and Annabelle McIver. 2019. Generalised differen- tial privacy for text document processing. InPrinciples of Security and Trust: 8th International Conference, POST 2019, Held as Part of the European Joint Conferences on Theory and Practice of Soft...

2019
[16]

Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe. 2020. Privacy- and utility-preserving textual analysis via calibrated multivariate perturbations. InProceedings of the 13th international conference on web search and data mining. 178–186

2020
[17]

Oluwaseyi Feyisetan, Tom Diethe, and Thomas Drake. 2019. Leveraging hier- archical representations for preserving privacy and utility in text. In2019 IEEE International Conference on Data Mining (ICDM). IEEE, 210–219

2019
[18]

Russell L Herman. 2015. Introduction to partial differential equations.North Carolina, NC, USA: RL Herman(2015)

2015
[19]

Timour Igamberdiev and Ivan Habernal. 2023. DP-BART for Privatized Text Rewriting under Local Differential Privacy. InThe 61st Annual Meeting Of The Association For Computational Linguistics

2023
[20]

Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov. 2017. Bag of Tricks for Efficient Text Classification. InProceedings of the 15th Confer- ence of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers, Mirella Lapata, Ph...

2017
[21]

Parameswaran Kamalaruban, Victor Perrier, Hassan Jameel Asghar, and Mo- hamed Ali Kaafar. 2020. Not all attributes are created equal: dx-private mecha- nisms for linear queries.Proceedings on Privacy Enhancing Technologies(2020)

2020
[22]

Yansong Li, Zhixing Tan, and Yang Liu. 2023. Privacy-preserving prompt tuning for large language model services.arXiv preprint arXiv:2305.06212(2023)

2023
[23]

Justus Mattern, Benjamin Weggenmann, and Florian Kerschbaum. 2022. The Limits of Word Level Differential Privacy. InFindings of the Association for Compu- tational Linguistics: NAACL 2022, Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz (Eds.). Associa...

2022 doi
[24]

Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient Esti- mation of Word Representations in Vector Space. In1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings. http://arx...

2013 arXiv
[25]

2017.Probability and computing: Random- ization and probabilistic techniques in algorithms and data analysis

Michael Mitzenmacher and Eli Upfal. 2017.Probability and computing: Random- ization and probabilistic techniques in algorithms and data analysis. Cambridge university press

2017
[26]

Alexander McFarlane Mood. 1950. Introduction to the Theory of Statistics. (1950)

1950
[27]

2006.Metric spaces

Mícheál O’Searcoid. 2006.Metric spaces. Springer Science & Business Media

2006
[28]

Shuchao Pang, Zhigang Lu, Haichen Wang, Peng Fu, Yongbin Zhou, Minhui Xue, and Bo Li. 2024. Reconstruction of Differentially Private Text Sanitization via Large Language Models.arXiv preprint arXiv:2410.12443(2024)

2024
[29]

Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014. Glove: Global vectors for word representation. InProceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 1532–1543

2014
[30]

1988.Numerical recipes

William H Press, William T Vetterling, Saul A Teukolsky, and Brian P Flannery. 1988.Numerical recipes. Cambridge University Press, London, England

1988
[31]

Chen Qu, Weize Kong, Liu Yang, Mingyang Zhang, Michael Bendersky, and Marc Najork. 2021. Natural language understanding with privacy-preserving bert. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 1488–1497

2021
[32]

Saiteja Utpala, Sara Hooker, and Pin-Yu Chen. 2023. Locally Differentially Private Document Generation Using Zero Shot Prompting. InConference on Empirical Methods in Natural Language Processing

2023
[33]

2019.High-dimensional statistics: A non-asymptotic view- point

Martin J Wainwright. 2019.High-dimensional statistics: A non-asymptotic view- point. Vol. 48. Cambridge university press

2019
[34]

Zekun Xu, Abhinav Aggarwal, Oluwaseyi Feyisetan, and Nathanael Teissier
[35]

Xiang Yue, Minxin Du, Tianhao Wang, Yaliang Li, Huan Sun, and Sherman S. M. Chow. 2021. Differential Privacy for Text Analytics via Natural Text Sanitization. InFindings of the Association for Computational Linguistics: ACL-IJCNLP 2021. Online, 3853–3866. doi:10.18653/v1/2021....

2021 doi
[36]

2023.Dive into deep learning

Aston Zhang, Zachary C Lipton, Mu Li, and Alexander J Smola. 2023.Dive into deep learning. Cambridge University Press

2023
[37]

Arthur Zimek, Erich Schubert, and Hans-Peter Kriegel. 2012. A survey on unsu- pervised outlier detection in high-dimensional numerical data.Statistical Analysis and Data Mining: The ASA Data Science Journal5, 5 (2012), 363–387. A Proofs Proof of Theorem 2. Proof. ∥w∗−y∥ 2 >∥w ...

2012
[42]

Thus,𝑦′′ > 0

The remaining term is positive since the exponential function is greater than 0 for any value of𝑡, and1−𝑡/𝜖 is also greater than 0if0 <𝑡<𝜖 . Thus,𝑦′′ > 0. Hence the function𝑦 is minimized at this value of𝑡. Putting this value of𝑡 into the expression for𝑦, we get the first stat...
[2020]

InProceedings of the Second Workshop on Privacy in NLP

A Differentially Private Text Perturbation Method Using Regularized Mahalanobis Metric. InProceedings of the Second Workshop on Privacy in NLP. 7–17
[2023]

InProceedings of the 2023 SIAM International Conference on Data Mining (SDM)

Tem: High utility metric differential privacy on text. InProceedings of the 2023 SIAM International Conference on Data Mining (SDM). SIAM, 883–890

2023
[2024]

Preempting Text Sanitization Utility in Resource-Constrained Privacy- Preserving LLM Interactions.arXiv preprint arXiv:2411.11521(2024)

2024 arXiv
[2025]

InPETS 2025-25th Privacy En- hancing Technologies Symposium

Enhancing metric privacy with a shuffler. InPETS 2025-25th Privacy En- hancing Technologies Symposium

2025

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

2001.Understanding analysis

Stephen Abbott et al. 2001.Understanding analysis. Vol. 2. Springer

work page 2001

[2] [2]

Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. 2001. On the surprising behavior of distance metrics in high dimensional space. InDatabase theory—ICDT 2001: 8th international conference London, UK, January 4–6, 2001 proceedings 8. Springer, 420–434

work page 2001

[3] [3]

Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catus- cia Palamidessi. 2013. Geo-indistinguishability: Differential privacy for location- based systems. InProceedings of the 2013 ACM SIGSAC conference on Computer & 13 Proceedings on Privacy Enhancing Technologies YYYY(X) Hassan Jameel Asghar, Robin Carpentier, Benjamin Zi Hao Zhao...

work page 2013

[4] [4]

Andreas Athanasiou, Konstantinos Chatzikokolakis, and Catuscia Palamidessi

work page

[5] [5]

nearest neighbor

Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When is “nearest neighbor” meaningful?. InDatabase Theory—ICDT’99: 7th International Conference Jerusalem, Israel, January 10–12, 1999 Proceedings 7. Springer, 217–235

work page 1999

[6] [6]

Sayan Biswas and Catuscia Palamidessi. 2023. PRIVIC: A privacy-preserving method for incremental collection of location data.Proceedings on Privacy En- hancing Technologies2024, 1 (2023), 582–596

work page 2023

[7] [7]

2020.Foundations of data science

Avrim Blum, John Hopcroft, and Ravindran Kannan. 2020.Foundations of data science. Cambridge University Press

work page 2020

[8] [8]

Robin Carpentier, Benjamin Zi Hao Zhao, Hassan Jameel Asghar, and Dali Kaafar

work page