PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations

Dung Nguyen, Anil Vullikanti

arXiv:2610.11870v1cs.DScs.CR

TL;DR

Finite-range private selection needs a principled way to use dataset-dependent sensitivity instead of the worst-case global scale. The paper develops private upper-scale, adaptive PTR, and smooth-sensitivity calibrations; its graph-selection application reports significantly better regret bounds than worst-case bounds for sparse Erdős–Rényi graphs under stated density assumptions.

  • Problem

    The paper asks how local sensitivity and related concepts can calibrate finite-range private selection with rigorous utility bounds, rather than relying on global sensitivity.

    Source: §1 · p. 3

  • Method

    The paper develops private high-probability local-sensitivity upper scales, adaptive PTR search, and smooth-sensitivity envelope and score-transform designs for exponential selection.

    Source: §1 · p. 4, §1.1 · p. 4, §6 · p. 16

  • Results

    For sparse Erdős–Rényi graphs under reasonable edge-density assumptions, the methods yield significantly better high-probability regret bounds than worst-case bounds.

    Source: §1.1 · p. 5, §10 · p. 26

  • Takeaways & Limitations

    The proposed mechanisms have instance-specific regret bounds that use local geometric properties of private input datasets.

    Source: §10 · p. 26

    Higher-order calibration helps only when its resulting upper scale is smaller, while each level consumes privacy and adds failure probability.

    Source: §5 · p. 15

Abstract

from arXiv · show

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.

1 Introduction

The paper asks when local sensitivity can safely replace global sensitivity in finite-range private selection, and develops calibrated alternatives with regret guarantees. Its contributions include private upper scales, adaptive PTR search, smooth-sensitivity designs, and graph-selection applications.

1.1 Contributions

  • Directly replacing global sensitivity with local or smooth sensitivity can fail to guarantee privacy, motivating carefully calibrated alternatives.The paper gives counterexamples for local sensitivity and for fixed smoothness and temperature coefficients in smooth sensitivity.Source: §1.1 · p. 4
  • A private, high-probability upper bound on local sensitivity supports approximate-DP exponential selection and can extend recursively to higher-order sensitivity hierarchies.Each level uses a private high-probability bound on its own local sensitivity, with privacy and failure probability accumulating across levels.Source: §1.1 · p. 4, §1 · p. 4
  • An adaptive PTR method privately searches for a safe temperature scale instead of relying on a fixed, difficult-to-set proposed bound.The introduction describes binary search using a 1-Lipschitz lower bound on distance to unsafe datasets.Source: §1.1 · p. 4, §1 · p. 4
  • A smooth geometric envelope and a logarithmic co-transformation yield pure DP while preserving utility maximizers, with instance-dependent regret bounds.The envelope is admissible under local dampening; the separate logarithmic design transforms both the score and smooth sensitivity.Source: §1.1 · p. 4
  • Two further smooth-sensitivity selectors provide approximate DP: direct Gibbs calibration with range- and privacy-dependent smoothness, and calibration through a privatized smooth scale.The direct method's smoothness requirement matches a theoretical lower bound up to constants depending only on ε.Source: §1.1 · p. 4
  • The paper proves regret bounds for its methods and lower bounds on temperature scales needed for privacy under unequal neighboring-dataset scales and direct smooth-sensitivity calibration.The introduction also notes that higher-order calibration is not always better: it helps only when its resulting upper scale is smaller, while consuming privacy and failure probability at each level.Source: §1.1 · p. 5
  • On Erdős–Rényi graphs under reasonable edge-density assumptions, local-sensitivity calibration gives significantly better high-probability regret bounds than worst-case bounds when graphs are sparse.The application selects a vertex or induced subgraph containing the maximum number of copies of a motif.Source: §1.1 · p. 5

1.2 Structure of the paper

  • The paper organizes its preliminaries, related work, failure analysis, calibration methods, and quantitative analysis before presenting graph-selection applications; Table 1 summarizes privacy and utility properties.Section 9 demonstrates improvements for vertex and subgraph selection in some input regimes.Source: §1.2 · pp. 5–6, §1.1 · p. 5, Table 1 · p. 5

2 Preliminaries

The preliminaries define the dataset graph, privacy model, candidate scores, sensitivity, and regret used throughout the paper. They also state the standard Gibbs/EM calibration and characterize smooth upper bounds.

2 Preliminaries

  • A dataset graph represents possible datasets as vertices and privacy-model neighbors as edges, making shortest-path distance a model-independent way to describe dataset proximity.For disconnected datasets the distance is infinite; the graph should not be confused with a graph-valued dataset's own edit-distance structure.Source: §2 · p. 6
  • Differential privacy requires output distributions on every neighboring-dataset edge to remain close, with δ = 0 corresponding to pure ε-DP.The definition is stated for ordered edges and measurable output events.Source: §2 · p. 6
  • For a finite public candidate range, score oscillation measures the maximum candidate-score change across an edge, while regret measures utility lost relative to a maximizer.Element, local, and global sensitivities quantify score change at different scopes.Source: §2 · pp. 6–7
  • The categorical Gibbs law favors higher-scoring candidates, and standard EM sets its public scale to global sensitivity; larger scales flatten sampling and worsen accuracy.Sensitivity scales used as denominators or noise scales are assumed finite, with a public floor providing positivity where needed.Source: §2 · p. 7
  • A dataset-dependent random-scale EM samples a scale first and then samples a candidate conditionally, while the mechanism must specify whether it releases the scale.The scale kernel may depend on the private dataset.Source: §2 · p. 7
  • A β-smooth upper bound dominates local sensitivity and changes by at most a multiplicative e^β across neighboring datasets; the minimal such bound is pointwise no larger than any other valid one.The minimal bound may be infinite, and positive-result mechanisms using it assume finiteness; privacy proofs need not use the minimal choice.Source: §2 · pp. 7–8

3 Related work

Prior work developed sensitivity-based private selection through several distinct mechanisms, but does not resolve the paper's all-candidate, dataset-dependent EM calibration setting. The authors situate their methods relative to PTR, smooth sensitivity, and perturb-and-select approaches.

3 Related work

  • The paper targets EM calibrated by a sensitivity that depends on the dataset and is common across candidates, unlike generalized EM with public per-candidate sensitivities.Prior work also applies local sensitivity hierarchies to private graph statistics.Source: §3 · pp. 8–9
  • PTR tests distance to datasets whose local sensitivity exceeds a proposed bound, then releases using that bound or abstains; prior fixed-scale EM-PTR relies on a public bound.A prior numeric-query approach uses noisy binary search and 1-Lipschitz lower certificates for distance.Source: §3 · p. 9
  • Earlier smooth-sensitivity counterexamples used fixed parameter choices; this paper strengthens the result to rule out any fixed positive smoothness and temperature coefficient for all finite candidate ranges.The strengthened obstruction excludes every finite ε and δ < 1 guarantee under those fixed choices.Source: §3 · p. 9
  • Other smooth-sensitivity selection frameworks use oracle calls, continuous Gibbs posteriors, or public candidate-specific sensitivities rather than this paper's finite-candidate dataset-specific calibration.A related continuous formulation assumes Euclidean, convex/Lipschitz-loss, and strongly log-concave-prior conditions.Source: §3 · p. 9
  • Perturb-and-select privatizes utility scores before argmax or sampling; smooth-noise approaches can require norm-specific analysis and candidate-range-dependent calibration.Related work also uses common smooth upper bounds to privatize scores for several selection tasks.Source: §3 · p. 10

4 Why direct data-dependent scales fail

Directly replacing the public EM scale with local or smooth sensitivity while leaving scores unchanged does not provide the claimed privacy guarantees. The section establishes distinct failure modes for local sensitivity and fixed-parameter smooth sensitivity.

4 Why direct data-dependent scales fail

  • Direct scale substitution keeps the utility score intact but replaces the public scale with dataset-dependent local or smooth sensitivity, without itself providing a privacy guarantee.The authors analyze this substitution separately for local sensitivity and smooth sensitivity.Source: §4 · p. 10

4.1 Local sensitivity

  • For every ε > 0, direct local-sensitivity scaling lacks a uniform (ε, δ)-DP guarantee for δ < 1/2, even when its denominator is positive at every mechanism dataset.The construction exploits arbitrarily different local sensitivities at neighboring datasets whose score vectors are identical, forcing δ toward 1/2.Source: §4.1 · pp. 10–11

4.2 Smooth sensitivity

  • Direct smooth-sensitivity scaling need not be pure ε-DP, because smoothness bounds scale ratios but cannot bound the resulting probability ratio for all score magnitudes.The probability ratio can be unbounded as a score parameter grows, even with a public positive smoothness value and the exact minimal smooth upper bound.Source: §4.2 · p. 11
  • For any fixed positive temperature coefficient and smoothness, multiplicity amplification rules out every finite-ε approximate-DP guarantee with δ < 1 over all finite candidate ranges.The neighboring datasets in the construction have identical score vectors, while their exact minimal smooth scales differ by e^β.Source: §4.2 · pp. 11–12
  • This impossibility fixes β and λ independently of candidate-range size and privacy parameters, so it does not rule out calibrations that compute them from m, ε, and δ.The paper proposes such parameter-dependent calibration later.Source: §4.2 · p. 12

5 Private upper scales and sensitivity hierarchies

The section calibrates exponential selection with privately released upper scales for local sensitivity, then extends the approach to finite higher-order sensitivity hierarchies. These methods provide privacy and regret guarantees, but deeper hierarchies are not automatically more useful.

5 Private upper scales and sensitivity hierarchies

  • A privately released upper scale B for local sensitivity allows conditional exponential selection, with underestimation accounted for in the approximate-DP guarantee.If the scale is a pure εt-DP private upper bound, the joint release is (εt + εs, η)-DP.Source: §5 · pp. 12–13
  • When C > 0, a shifted-Laplace scale for LSq yields (εt + εs, η)-DP; when C = 0, the deterministic scale gives pure εs-DP.The shifted release uses noise scaled by C/εt and a shift to make it a high-probability upper bound.Source: §5 · p. 13
  • A finite sensitivity hierarchy uses levels H0 through Hk that upper-bound successive local sensitivities, with a finite public global-sensitivity cap at the top.The levels need not be exact local sensitivities; loose bounds can affect utility without affecting the privacy analysis.Source: §5 · p. 14
  • Recursive private-scale selection guarantees privacy for the joint release (B0, R), and the same statement holds when internal scales are also released.The recursive construction privately upper-bounds each level’s local sensitivity before using B0 to calibrate exponential selection.Source: §5 · pp. 14–15
  • The recursive selection method also gives a high-probability regret bound under its stated conditions.The bound is derived by propagating upper bounds down the hierarchy and combining them with the conditional exponential-mechanism tail.Source: §5 · p. 15
  • Higher-order calibration can be strictly better or worse than one-level calibration; it helps only when its resulting U0 is smaller than the one-level bound.Each level uses privacy and adds to the failure probability.Source: §5 · p. 15

6 Adaptive certificate-search PTR selection

This section replaces a fixed proposed sensitivity scale with a private search over a public grid, using lower certificates to test candidate scales. The resulting selector has a privacy guarantee and a certificate-dependent regret bound under stated conditions.

6 Adaptive certificate-search PTR selection

  • Certificate design and computational efficiency depend on the application and are not universally tractable.The section notes that each application may require a distinct lower-certificate design.Source: §6 · p. 15
  • A certificate may underestimate distance to the unsafe zone but must never overestimate it; monotonicity across grid indices is needed for the utility guarantee, not privacy.Truncated distance at a finite public threshold is one valid certificate, even when the exact distance is infinite.Source: §6 · p. 16
  • A private binary search over a public grid finds a candidate temperature scale using a 1-Lipschitz lower certificate for distance to unsafe datasets.The selected scale is used to calibrate the exponential mechanism, avoiding a fixed, arbitrary proposed upper bound.Source: §6 · pp. 15–16
  • The selected scale B is pure εt-DP, and the joint output (B, R) is (εt + εs, η)-DP.The guarantee also applies to R alone.Source: §6 · p. 16
  • The certificate-dependent regret guarantee requires a nonempty set of indices meeting the stated threshold and certificates nondecreasing in the grid index.The supplied proposition states the bound for this condition, with a further high-probability statement.Source: §6 · p. 17

7 Smooth Sensitivity

Section 7 develops smooth-sensitivity methods for private selection, including utility transformations and temperature calibrations. The transformations yield range-independent pure DP while preserving the original utility maximizers; the other approaches use smoothness to calibrate temperature.

7 Smooth Sensitivity

  • Smooth sensitivity supports both utility-score transformations and temperature calibration, with different privacy guarantees and design trade-offs.The transformations target bounded or controllable global sensitivity; the other approaches use smoothness or a privatized smooth upper scale for calibration.Source: §7 · p. 17

7.1 A geometric transformation of smooth sensitivity

  • The geometric smooth envelope is candidate-independent, preserves the original maximizers, and enables a pure ε-DP selector with a high-probability regret bound.The envelope is designed for the local dampening framework; smooth sensitivity alone does not satisfy its admissibility conditions.Source: §7.1 · pp. 18–19

7.2 A logarithmic co-transformation of smooth sensitivity and utility score

  • The logarithmic co-transformation has global sensitivity at most 1 + cβ, preserves all original maximizers, and yields pure ε-DP with a high-probability regret bound.The public tuning constant c controls the sensitivity bound and can be selected by optimizing the stated regret bound over a grid.Source: §7.2 · p. 20

7.3 Other approaches for smooth sensitivity

  • Section 7.3 gives direct smooth-sensitivity Gibbs calibration and privatization of a smooth upper scale, with approximate-DP and high-probability regret guarantees.The direct rule is calibrated to the candidate range and privacy parameters; the private-scale approach releases a privatized upper scale before selection.Source: §7.3 · pp. 20–22

8 Lower bounds

Section 8 gives lower bounds on temperature scales for private exponential selection, including a necessary smoothness condition for direct smooth-sensitivity calibration. These bounds constrain dataset-dependent scales and show the direct rule’s smoothness requirement grows stricter as the candidate range grows.

8 Lower bounds

  • The lower bounds cover deterministic scales and scales set by smooth sensitivity, and the direct smooth-sensitivity calibration matches the required smoothness up to constants depending on ε.The scale restrictions concern privacy for exponential selection across neighboring datasets.Source: §8 · p. 23
  • For neighboring datasets with reversed candidate preferences, pure DP jointly constrains their deterministic scales, since local sensitivities can differ arbitrarily.The paper relates this constraint to how its proposed methods control the scales or their distributions across neighboring datasets.Source: §8 · p. 23
  • When privacy parameters are fixed, direct smooth-sensitivity calibration requires β = O(1/log m) as the candidate range grows.Theorem 8.2 gives a necessary smoothness condition for the direct rule to satisfy approximate DP uniformly over finite gap scores.Source: §8 · pp. 23–24

9 Applications

The applications use privatized local-sensitivity bounds for motif-based vertex and k-set selection, comparing regret with global-sensitivity EM on Erdős–Rényi graphs.

Regret bounds

  • For Kℓ-participation vertex selection, the regret-gap ratio is Oℓ((D/n)^(ℓ−2) + log n/n) when ε = Θ(1), with asymptotic improvement when D = o(n).The comparison is against the worst-case global-sensitivity regret bound; the table caption defines the final column as this ratio.Source: Table 3 · p. 24, §9 · p. 26

Applications

  • The method privately upper-bounds local sensitivity and uses that bound in EM for vertex or induced-subgraph selection of motifs such as ℓ-cliques.The privacy guarantee does not depend on the Erdős–Rényi assumption; that assumption is used for the regret analysis.Source: §9 · pp. 24–25

Scope

  • The reported bound is Oℓ((D/n)ℓ−2 + log n/n) when ε = Θ(1); gaps show significant improvements when D = o(n), equivalently p = o(1), for participation-vertex problems.Source: §9 · p. 26

Regret bounds

  • The cited result states that D = o(k) is sufficient for improvements when Λ/(εk) = o(1).Source: §9 · p. 26

10 Conclusions

The conclusions distinguish unsafe direct sensitivity substitutions from adaptations that provide privacy and regret guarantees; the appendix proves a standard edgewise EM bound.

10 Conclusions

  • Directly replacing global sensitivity with local or smooth sensitivity at fixed smoothness does not guarantee privacy, even under approximate DP.The paper instead identifies privatized high-probability local-sensitivity bounds, adaptive PTR, and co-transformation of smooth sensitivity and utility as privacy-preserving adaptations.Source: §10 · p. 26
  • The proposed methods have regret bounds that use local geometric properties, and graph-selection applications improve on global-sensitivity bounds for a family of Erdős–Rényi graphs under stated density assumptions.The applications do not claim superiority to specialized state-of-the-art algorithms.Source: §10 · p. 26

A Proof for Section 2

  • The appendix proves the edgewise EM privacy bound by bounding changes in unnormalized weights and then bounding the normalization ratio.It applies when neighboring inputs have ωq(x, x′) ≤ b and bounds the likelihood ratio in both directions.Source: A Proof for Section 2 · p. 31

B Proof and further discussions of Section 6

This discussion gives a fixed-bound PTR mechanism for EM: a noisy test determines whether to run the selection mechanism or abstain.

Fixed-bound PTR

  • Fixed PTR tests a public bound b using a noisy distance-to-safety measure, runs Qb only after a pass, and otherwise outputs ⊥.The test is εt-DP, and unsafe edges contribute only their false-pass probability, yielding (εt + εs, δ)-DP with the EM step.Source: B Proof and further discussions of… · p. 31
  • Conditional on passing the fixed PTR test, the ordinary regret bound is 2b log(m/ρ)/εs.Source: B Proof and further discussions of… · p. 31
  • A fixed bound can lower test overhead when a good b is known, but a poorly chosen b may make the mechanism refuse to answer.The passage characterizes this fixed-bound result as a direct use of PTR, not a new result.Source: B Proof and further discussions of… · p. 31

C Proof and further discussions of Section 7

For an admissible envelope, the proof bounds changes in the transformed utility across neighboring datasets, allowing ordinary EM to yield pure differential privacy.

Admissible-envelope dampening

Proof

D Proof and further discussions of Section 9

The appendix proves privacy and regret guarantees for clique selection with a privately chosen scale, then extends the analysis to connected motifs and compares local-sensitivity bounds with full-budget global-sensitivity bounds.

D Proof and further discussions of Section 9

  • The selector splits ε equally between scale testing and sampling, draws a private scale B using Laplace noise, and samples candidates with weights exp{εq(G, r)/(4B)}.The privacy proof permits any public upper bound C ≥ GSL in place of the exact global sensitivity.Source: D Proof and further discussions of… · p. 32

Define the two edge-completion profiles

The corresponding full-budget global-sensitivity bounds are exactly

  • For triangle selection, the bounds can sharpen by replacing D with Γ and min{k, D} with min{k, Γ}.The proof uses the random-graph codegree bound κ(G) = O(Γ).Source: The corresponding full-budget… · p. 34
  • The analysis extends from cliques to fixed connected motifs using non-induced copies, which preserve motif edges but not non-edges.Algorithm 2 is (ε, η)-DP, with vertex and k-set regret guarantees holding with probability at least 1 − ζ − ξ − ρ on G(n, p).Source: The corresponding full-budget… · pp. 34–35
  • For non-induced motif counting, toggling an edge changes only copies using that edge, enabling local-sensitivity bounds based on edge-completion profiles.The proof contrasts this with induced embeddings, where adding an edge can invalidate a copy.Source: The corresponding full-budget… · pp. 34–35
Loading 2610.11870v1…