Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations

summary

The gist

The gist Selection is a task that chooses one element from a finite public candidate range to maximize a data-dependent score, and this paper studies when dataset-dependent sensitivity can safely

In short

The paper investigates when using data-dependent sensitivity can safely replace global sensitivity in private selection tasks where one chooses an element from a finite range to maximize a score. It demonstrates that naive applications of local or smooth sensitivities fail because neighboring datasets can have arbitrarily different local sensitivities, leading to poor privacy guarantees.

Key concepts

Local Sensitivity: This measures how much the output distribution changes when only one data point is changed in the input dataset. The paper shows that using local sensitivity directly to set a temperature scale in the Exponential Mechanism often fails to guarantee differential privacy because neighboring datasets can behave very differently.
Smooth Sensitivity: This approach uses a continuous function to approximate sensitivity, aiming for a more stable measure of output change. The authors explore various ways to use smooth sensitivity, including geometric envelope functions and logarithmic co-transformations, to control the global sensitivity and achieve better privacy guarantees.
Exponential Mechanism (EM): The EM is a technique used for private selection where the probability of selecting an item is proportional to its utility score raised to a temperature parameter. The paper focuses on calibrating this mechanism's temperature scale using local or smooth sensitivity to ensure the resulting selection process meets differential privacy standards.
$(\epsilon, \delta)$-DP: This is a formal privacy guarantee ensuring that the probability of any outcome being selected differs by at most $\epsilon$ across neighboring datasets, with a small probability $\delta$. The paper proves that certain direct sensitivity calibrations do not satisfy this guarantee when applied naively.

Terminology used across episodes

Reinforcement Learning (RL) — explained in 24 episodes
Retrieval-Augmented Generation (RAG) — explained in 16 episodes
Interpretability — explained in 15 episodes
Sample Complexity — explained in 15 episodes
Federated Learning — explained in 14 episodes
Generalization — explained in 13 episodes

This episode discusses

The paper

Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations · Read on arXiv

Dung Nguyen, Anil Vullikanti

University of Texas at San Antonio · University of Virginia

Selection is a task that chooses one element from a finite public candidate range to maximize a data-dependent score. In differential privacy (DP), the exponential mechanism (EM) samples a candidate at a temperature calibrated to the global sensitivity. In this paper, we study when dataset-dependent sensitivity can safely replace global sensitivity in private selection. We propose three valid approaches. First, a private, high-probability upper bound on local sensitivity yields approximate DP, and the method extends to finite higher-order sensitivity hierarchies. Second, our Propose-Test-Release (PTR) variant privately searches a finite public grid for a temperature scale rather than fixing it in advance. Third, smooth sensitivity supports several designs. A candidate-independent smooth geometric construction produces a sensitivity envelope that is admissible under the local dampening framework, which privacy is guaranteed for any admissible envelope. Additionally, a separate logarithmic transformation utilizes smooth sensitivity to produce a smoothed candidate score function with advantages: having controlled global sensitivity, and preserving the maximizers of the original utility score, i.e., candidates maximizing the utility. Both of the designs yield range-independent pure DP. Besides that, we also give two approximate DP private selectors using smooth sensitivity: a direct EM with smooth sensitivity calibrated to the candidate range and privacy parameters that matches a theoretical lower bound up to some constant factor, and one using a privatized smooth upper scale by analyzing the logarithmic transform of the smoothness. For every proposed mechanism, we derive a high-probability regret bound under its stated conditions.

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "Local Sensitivity in Exponential Selection".

Nadia: The gist Selection is a task that chooses one element from a finite public candidate range to maximize a data-dependent score,

Elias: First, who's behind it and why it matters.

Paper summary: Nadia: So we're looking at this paper now, "Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations." The main idea here is that when you try to use data-dependent sensitivity instead of global sensitivity for selection tasks under differential privacy, it can actually fail badly.

Elias: Exactly. They show that naive uses of local or smooth sensitivity don't work because the local sensitivities of two adjacent datasets can change wildly, even if their score vectors look the same.

Nadia: And they specifically prove that no smooth sensitivity calibrated by a fixed smoothness and a fixed temperature coefficient can guarantee range-independent epsilon-delta differential privacy. They use Proposition four point two to show that the probability ratio of returning the same candidate at an edge can't be bounded by the smoothness because when C gets really big, the ratio between exp(e beta C) and exp(C) just goes unbounded <ref:2610.11870#pg2>.

Priya: So what does this actually mean for us in terms of privacy? It means that relying on a simple local sensitivity estimate to set the temperature scale for the exponential mechanism isn't safe if you want your privacy guarantees to hold no matter where you are in the data space.

Nadia: Right, and they don't stop there. They propose three different ways to fix this problem with valid calibrations. First, a private upper bound on local sensitivity can give you approximate differential privacy, and that method even works for finite higher-order sensitivity hierarchies <ref:2610.11870#pg2>.

Elias: Then there's the Propose-Test-Release or PTR variant, where they privately search a finite public grid for a temperature scale instead of picking one ahead of time <ref:2610.11870#pg2>. And finally, smooth sensitivity can be used in different ways too, like with geometric constructions or logarithmic co-transformations to get a smoothed candidate score function with controlled global sensitivity <ref:2610.11870#pg3>.

Priya: I'm curious about the numbers. If we look at the results, they show that for some problems, like finding a vertex or an induced subgraph that is included in the maximum number of copies of a motif H, such as an l-clique <ref:2610.11870#pg3>, their regret bounds for Erdős–Rényi graphs G(n, p) show significant improvements over the worst-case global sensitivity regret bounds <ref:2610.11870#pg3>.

Nadia: That improvement is what they're pointing toward—showing that these methods can actually beat the worst-case global sensitivity results when you're dealing with common graph structures and edge densities greater than twenty-six <ref:2610.11870#pg3>.

Elias: It seems like the core focus is moving from a fixed global scale to something more adaptive that accounts for the data itself, which is what this paper is all about.

Priya: So, if you're just listening and you're thinking about using these for privacy-preserving selections in real-world data analysis, this paper tells you that you have to be careful with how you set your sensitivity calibration; it can be a huge difference between what’s theoretically possible and what actually gives you privacy.

Conclusion: Nadia: So, wrapping up the talk on "Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations," the authors Dung Nguyen and Anil Vullikanti are showing us that direct applications of local or smooth sensitivities in setting the temperature scale for the exponential mechanism aren't safe.

Elias: They established that local sensitivities require an additive privacy parameter delta close to one/two <ref:2610.11870#pg3>, and to get approximate differential privacy using a private upper bound on local sensitivity, they had to design a conditional EM and prove a recursive theorem for higher-order local sensitivity hierarchies <ref:2610.11870#pg3>.

Nadia: And that means the method they propose—the adaptive certificate-search PTR selection—it can yield a joint release that is (epsilon bar j + epsilon s, min

e epsilon s delta bar j + eta j, delta bar j + e epsilon bar j eta j, one: )-DP <ref:2610.11870#pg3>, which can be strictly better or worse than one-level calibration <ref:2610.11870#pg3>.

Elias: It really boils down to having these alternative utilizations of smooth sensitivity, like using a categorical Gibbs law directly calibrated by smooth sensitivity, and privatizing the smooth sensitivity itself <ref:2610.11870#pg3>.

Nadia: For someone just listening, what this means is that if you're building a privacy system for selecting items from private data, you can't just pick one fixed way to set your noise level; you have to use a method that adapts based on the data or search space.

Priya: That’s right. It shows that controlling how fast the universe is expanding near us—or in this case, controlling the sensitivity—is much more complex than it looks when you just plug in a simple formula.

More episodes

← Home