PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Kernel Mechanisms for Locally Differentially Private Discrete Channels

Amirreza Zamani, Parastoo Sadeghi, Mikael Skoglund

arXiv:2610.07993v1cs.ITmath.IT

TL;DR

Sparse locally private channels restrict each input to a small output support, creating a privacy-accounting challenge when supports vary. The paper gives exact sparse-kernel privacy characterizations and applies them to discrete mechanisms; pure LDP requires coincident supports, while approximate privacy separates leakage from overlap loss.

  • Problem

    Sparse channels restrict outputs to small admissible sets, but the privacy effect of input-dependent supports requires exact accounting.

    Source: §I · p. 1

  • Method

    The paper characterizes privacy for nonnegative kernels with input-dependent supports and decomposes approximate privacy defect into support leakage and overlap excess loss.

    Source: §III · p. 3, §IX · p. 9

  • Results

    Pure LDP requires coincident supports, whereas approximate LDP permits mismatch through support leakage and an exact overlap contribution.

    Source: §I · p. 1, §III · p. 3

  • Takeaways & Limitations

    Sparse mechanism design must balance support size and overlap while controlling kernel likelihood ratios on shared outputs.

    Source: §IX · p. 10

Abstract

from arXiv · show

We study sparse locally private discrete mechanisms generated by a nonnegative kernel and an input-dependent admissible output support. The support set is intentionally small relative to the ambient alphabet and acts as a mechanism-design parameter. This formulation covers metric-ball supports, sparse exponential mechanisms, sparse staircase mechanisms, sparse randomized response, sparse additive kernels such as Skellam perturbations, and Poisson-binomial-inspired bounded-support channels. We give a general exact characterization of pure and approximate local differential privacy for this sparse-kernel class. Pure local differential privacy forces all supports to coincide, so genuinely input-dependent sparse supports are incompatible with pure privacy. In the approximate regime, the privacy defect decomposes exactly into support leakage and overlap excess loss. We instantiate the formula for several discrete mechanism families. For sparse staircase mechanisms, a shell-ratio condition eliminates overlap excess loss. For graph-metric supports, overlap of metric balls is necessary for nontrivial privacy. For sparse randomized response, the support-leakage term has a closed form in terms of support mismatch. For generic radius-truncated additive kernels and, in particular, sparse Skellam mechanisms, we obtain exact finite-support formulas in terms of the Skellam CDF and an exact Bessel-ratio overlap condition. Numerical evaluations illustrate how support radius and kernel shape separately affect support leakage and overlap excess loss.

I. INTRODUCTION

Sparse local channels restrict each input to a small admissible output set, making support mismatch part of privacy accounting. The paper develops exact sparse-kernel privacy accounting and applies it to discrete mechanism families.

I. INTRODUCTION

  • Sparse supports concentrate probability on plausible outputs and can reduce distortion and communication, but input-dependent supports violate pure LDP and consume the approximate δ budget.The introduction frames support mismatch as a privacy-relevant design choice, not merely a modeling detail.Source: §I · p. 1

B. Related work

  • Prior work studied radius-truncated sparse Laplace and Gaussian tradeoffs [1], while this paper focuses on exact privacy effects across a broader range of discrete kernels.Related work also covers statistical estimation,, and divergence-based LDP characterizations [18].Source: §I · p. 1, B. Related work · p. 2

A. Positioning and novelty

  • The paper separates privacy defect into support leakage and overlap excess loss, then applies this accounting to kernels with intentionally restricted supports.The framework is presented as useful when the range is finite, communication is limited, or only nearby outputs are meaningful.Source: A. Positioning and novelty · pp. 1–2

C. Contributions

  • The contributions include an exact characterization for nonnegative kernels and input-dependent supports, with approximate loss split between mismatched outputs and excessive likelihood ratios on shared outputs.The paper also instantiates the framework for sparse exponential, staircase, randomized-response, Skellam, and Poisson-binomial-inspired channels.Source: C. Contributions · p. 2
  • For staircase mechanisms, a shell-ratio condition removes overlap excess loss; for radius-truncated Skellam mechanisms, leakage has an exact CDF formula and overlap obeys a Bessel-ratio condition.Finite-sum numerical evaluations examine how support radius and kernel shape separately affect leakage and overlap excess loss.Source: C. Contributions · p. 2

II. PRELIMINARIES

  • The preliminaries use the discrete hockey-stick divergence characterization of approximate LDP and allow privacy to be required only for pairs in a symmetric relation.The usual all-pairs definition is the special case where the relation contains every input pair.Source: §II · p. 2

III. SPARSE KERNEL MECHANISMS

The sparse-kernel class pairs a nonnegative kernel with an input-dependent admissible output support. Its exact privacy accounting distinguishes support leakage from excess loss on the overlap.

III. SPARSE KERNEL MECHANISMS

  • The mechanism class uses a nonnegative kernel on each nonempty admissible support, normalized by its kernel mass.The support size |S(x)| is the sparsity level.Source: §III · p. 3
  • Pure ε-LDP holds exactly when all inputs share a support and the kernel likelihood ratios satisfy the stated bound on that support.For a symmetric relation, the support and ratio conditions apply to each required pair.Source: §III · p. 3
  • Approximate privacy holds exactly when the supremum of the defect is at most δ, with the defect split into support leakage and overlap excess loss.The support-leakage term covers outputs allowed under x but not x′; overlap excess loss accounts for kernel differences on shared outputs.Source: §III · p. 3
  • Genuinely input-dependent supports cannot satisfy pure ε-LDP for finite ε, while mismatch contributes directly to the approximate δ budget.On a relation, differing supports in separate connected components do not violate pure privacy constraints imposed only on required pairs.Source: §III · p. 3
  • The support map determines which outputs create leakage, while the kernel determines likelihood ratios on the overlap.Enlarging supports often reduces leakage by increasing overlap, but can expose more outputs to overlap comparison.Source: §III · p. 4

A. Metric and graph-ball supports

Metric-ball supports restrict outputs to points within a chosen radius of the input. Overlap of the balls is necessary, though not sufficient, for nontrivial privacy on the required relation.

A. Metric and graph-ball supports

  • Metric-ball supports consist of outputs within radius r of the input; graph balls use shortest-path distance on graph vertices.The sparsity cost depends on ball cardinality, which can grow differently across geometries.Source: A. Metric and graph-ball supports · p. 4
  • Disjoint metric-ball supports give ordered privacy defect exactly one, making any δ < 1 bound impossible for that pair.Thus every required pair must have overlapping balls for nontrivial approximate privacy.Source: A. Metric and graph-ball supports · p. 4
  • Overlap alone does not guarantee a privacy budget: support leakage and overlap excess loss must still sum to at most δ for every required pair.Ball cardinalities may grow slowly on a path or grid but exponentially on a high-degree tree.Source: A. Metric and graph-ball supports · p. 4

IV. SCORE, SHELL, AND RANDOMIZED-RESPONSE KERNELS

The sparse exponential mechanism restricts score-based sampling to an admissible support. Its privacy conditions combine score variation and normalization on shared supports, while support mismatch remains a separate source of leakage.

A. Sparse exponential mechanisms

  • The sparse exponential mechanism uses kernel Kη(x, y) = e^ηu(x,y), restricting score-based sampling to the chosen support.The parameter η controls how strongly high-utility outputs are favored.Source: A. Sparse exponential mechanisms · p. 4
  • With common support and input-independent normalizers, ηΔu ≤ ε is sufficient for pure ε-LDP when score sensitivity is bounded by Δu.The stated sensitivity bound is sup over x, x′, and y of |u(x,y) − u(x′,y)| ≤ Δu.Source: A. Sparse exponential mechanisms · p. 4
  • Equal normalizers do not remove leakage when supports differ.The pure-privacy equivalence for this mechanism is stated under common support.Source: A. Sparse exponential mechanisms · p. 4

B. Sparse staircase mechanisms

Sparse staircase mechanisms assign weights by distance shell on metric-ball supports. A shell-ratio condition eliminates overlap excess loss for sufficiently nearby input pairs.

B. Sparse staircase mechanisms

  • The sparse staircase kernel assigns shell weights according to distance from the input and is defined over radius-r supports.The weights are zero-extended beyond radius r; each support is assumed nonempty and its normalizer finite.Source: B. Sparse staircase mechanisms · p. 4
  • Proposition 3 states that the sparse staircase mechanism with kernel K(x,y)=ad(x,y) and the stated zero extension satisfies Theorem 1; under common support S, pure ε-LDP has an iff characterization.The supplied passage ends after “if and only if” and does not show the condition.Source: B. Sparse staircase mechanisms · p. 5
  • A shell-ratio condition makes the overlap excess-loss contribution zero for every pair whose ambient distance is at most H.The condition covers both ordered pairs through its range over (j, k) and (k, j).Source: B. Sparse staircase mechanisms · p. 5
  • Sparse discrete-Laplace mechanisms are a special staircase family; the broader family allows the shell profile to be designed rather than fixed by one inverse-temperature parameter.For empty overlap, the overlap sum is zero, but support leakage is one.Source: B. Sparse staircase mechanisms · p. 5

C. Sparse randomized response as a kernel instance

The section specializes sparse-kernel privacy accounting to piecewise-constant sparse randomized response and translation-invariant additive kernels, identifying support conditions and exact defect structure.

C. Sparse randomized response as a kernel instance

  • For q > 0, the channel’s actual support is S(x), with probability p at x and q at each other supported output; for q = 0 it reduces to {x}.The proposition gives an exact approximate-privacy defect for this channel, with its ordered defect depending on support mismatch.Source: C. Sparse randomized response as a… · p. 5
  • With common supports and at least two inputs, sparse randomized response is pure ε-LDP exactly when p ≤ e^εq; q = 0 admits no finite pure-privacy guarantee.For q > 0, the condition is equivalently p/q ≤ e^ε.Source: C. Sparse randomized response as a… · p. 5

A. Translation-invariant additive kernels

  • Radius-truncated translation-invariant additive kernels admit an exact defect formula, and the result depends only on the absolute separation of the input centers.The result covers symmetric pmfs, including kernels with zero masses inside the truncation window.Source: A. Translation-invariant additive… · pp. 5–6
  • For additive kernels, disjoint windows at separation h > 2r give defect one, while identical centers give defect zero.The Skellam specialization expresses support leakage through its CDF and overlap excess loss through an exact Bessel-ratio condition.Source: A. Translation-invariant additive… · p. 6

B. Sparse Skellam mechanisms

The paper applies sparse-kernel accounting to Skellam noise and derives finite-radius formulas for support leakage and overlap excess loss, including an exact condition for positive overlap loss.

B. Sparse Skellam mechanisms

  • The sparse Skellam mechanism is an instance of the general sparse-kernel class with kernel Kµ(x, y) = ψµ(y − x).The symmetric Skellam pmf is strictly positive, so the mechanism’s normalizer is positive on every nonempty admissible support.Source: B. Sparse Skellam mechanisms · p. 6

C. Radius-truncated sparse Skellam mechanisms

  • For the radius-truncated symmetric Skellam law, the normalization probability is P[−r ≤ Z ≤ r] = Fµ(r) − Fµ(−r − 1) = 2Fµ(r) − 1 > 0.When h > 2r, the two supports are disjoint and the ordered privacy defect equals one.Source: C. Radius-truncated sparse Skellam… · p. 6
  • The total radius-truncated defect combines the CDF-based support-leakage mass with the overlap excess-loss term.Symmetry gives the same defect for the reverse ordered pair, without requiring monotonicity in separation.Source: C. Radius-truncated sparse Skellam… · p. 7
  • On overlapping supports, the Skellam pointwise privacy loss is determined by a ratio of modified Bessel functions.Overlap excess loss is positive exactly when at least one overlap index satisfies the stated Bessel-ratio threshold; otherwise it is zero.Source: C. Radius-truncated sparse Skellam… · p. 7
  • A Gaussian-style threshold is not generally a substitute for the exact Bessel-ratio condition: its approximation is accurate only in an appropriate central-limit regime.For fixed ε > 0 and h, a formal Gaussian threshold can fall outside that regime.Source: C. Radius-truncated sparse Skellam… · p. 7

D. Poisson-binomial-inspired sparse channels

The paper treats Poisson-binomial pmfs as bounded-support sparse-kernel templates and applies the same privacy accounting, subject to positivity on the chosen support.

D. Poisson-binomial-inspired sparse channels

  • A Poisson-binomial pmf βx(y) serves as a bounded-support kernel template for a sparse local channel, not as an additive single-user perturbation.The channel is defined on a nonempty admissible support of positive-mass outputs.Source: D. Poisson-binomial-inspired sparse… · p. 7
  • Under the positive-support assumption, the channel satisfies the sparse-kernel theorem and has an exact approximate-privacy defect.The defect separates contributions from outputs in S(x) \ S(x′) and from outputs in the supports’ intersection.Source: D. Poisson-binomial-inspired sparse… · p. 7
  • The displayed logarithmic bound implies the pointwise pure-privacy inequality and is necessary under the stated support assumptions.The logarithmic expression may be undefined without positivity on the stated support.Source: D. Poisson-binomial-inspired sparse… · pp. 7–8

VI. NUMERICAL ILLUSTRATIONS

The numerical illustrations evaluate the derived formulas exactly over a bounded input-separation relation and distinguish support leakage from overlap excess loss.

VI. NUMERICAL ILLUSTRATIONS

  • The experiments are exact finite-sum evaluations, not Monte Carlo simulations.They report the worst ordered defect over RH = {(x, x′): 1 ≤ |x − x′| ≤ H} on the integer line.Source: §VI · p. 8
  • The reported guarantee applies on RH, not globally over all integer pairs, because arbitrarily distant pairs give defect one for finite-radius mechanisms.Translation invariance and symmetry identify both ordered directions with the same positive separation.Source: §VI · p. 8
  • The plots aim to separate support leakage from overlap excess loss and show how support radius affects these terms.The experiments also report a first-distance moment, which is independent of x in the translation-invariant examples.Source: §VI · p. 8

A. Calibrated sparse randomized-response baseline

The calibrated sparse randomized-response baseline applies the common-support ratio p_t/q_t = e^ε to shifting line-supported outputs. Its exact approximate defect increases with input separation, while increasing support size trades lower privacy defect for greater expected reporting distance.

A. Calibrated sparse randomized-response baseline

  • When supports shift with the input, pure LDP fails unless the supports coincide; approximate privacy is instead measured by the exact defect over 1 ≤ h ≤ H.The calibration p_t/q_t = e^ε holds for a common support.Source: A. Calibrated sparse… · p. 8
  • The truthful overlap contributes no excess loss because p_t = e^εq_t, and the nondecreasing defect expressions attain their range maximum at h = H.The support difference has h points for h ≤ 2t; it excludes the truthful point for h ≤ t and includes it for h > t.Source: A. Calibrated sparse… · p. 8
  • The randomized-response formulas reproduce the corresponding columns of Table I.Source: A. Calibrated sparse… · p. 8
  • For (ε, H) = (1, 3), the defect equals one when neighboring supports are disjoint, then decreases as support size grows enough to ensure overlap throughout the range.Expected reporting distance grows as probability mass spreads across more possible outputs.Source: A. Calibrated sparse… · p. 8

B. Radius-truncated sparse Skellam decomposition

The radius-truncated Skellam evaluation separates support leakage from overlap excess loss, which move differently as support size grows. The broader design discussion applies this accounting across sparse-kernel instances and recommends balancing support overlap with control of likelihood ratios.

B. Radius-truncated sparse Skellam decomposition

  • For (ε, µ, H) = (1, 2, 3), support leakage decreases rapidly as support grows, while overlap excess loss rises and stabilizes, leaving total defect near a plateau.Separating the components reveals why the plateau near 0.553 persists even as support leakage is almost eliminated and overlap loss becomes dominant.Source: B. Radius-truncated sparse Skellam… · p. 8, Figure 1 · p. 9

VII. FURTHER DESIGN IMPLICATIONS

  • The design checks are to avoid disjoint neighboring supports, control likelihood ratios on their overlap, and balance support size against kernel shape.The cited text identifies shell-ratio constraints for shell kernels, a noise-pmf ratio condition for additive kernels, and an exact Bessel-ratio condition for Skellam kernels.Source: §VII · pp. 8–9

IX. DISCUSSION AND CONCLUSION

  • The framework separates the kernel's control of relative probabilities on overlapping supports from the support map's control of sparsity and support leakage; pure LDP requires input-independent supports.For Skellam, the leakage term has a CDF form, while the overlap term uses a Bessel-ratio condition; the design principle is to keep supports sufficiently overlapping and control overlap likelihood ratios.Source: §IX · pp. 9–10

VIII. SUMMARY OF MECHANISM INSTANCES

  • The covered instances include metric-ball supports, sparse exponential and staircase mechanisms, randomized response, Skellam noise, and Poisson-binomial-inspired bounded-support channels.They share the support obstruction and approximate-defect decomposition; the kernel-specific overlap term differs.Source: §VIII · p. 9, §IX · p. 10
Loading 2610.07993v1…