Marginal counts are rounded to float32 before noise, which increases sensitivity for large values

Aperta
  • Qualcosa non va?
#290 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
48/100
Tipo di issue
Bug
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
numpy, python
Ambito
backend, databases, security

Direzione di ricerca

Start by tracing how discrete-mechanism marginals pass through data.project() into an mbi Factor, and where sensitivity is computed relative to noise. Reproduce the reported discrepancy with the weighted dataset in the issue, then identify a representation and sensitivity calculation that preserve the intended neighboring-dataset bound. Done means the released marginal satisfies the stated differential privacy guarantee for the large-count example.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

Every discrete-mechanism marginal goes through data.project(), which converts it to an mbi Factor, which is implicitly stored in float32 by default. For large numbers of records, the floating-point imprecision has an influence on the sensitivity: the ulp after 2²⁴ is 2, the ulp after 2²⁵ is 4, etc., so adding single element can lead to a larger-than-1 increase in the float32 representation.

To observe the issue, we don't need to build a massive dataset, we can just use the weights parameter in the input dataset to emulate what would happen if a specific value was present 2²⁶+4 or 2²⁶+5 times — values that will be rounded to 2²⁶ and 2²⁶+8, respectively. The sensitivity mismatch makes it easy to retrieve the original database.

import math
import mbi
import numpy as np
import dpsynth
from dpsynth.discrete_mechanisms import common

# one binary column: D has 2^26 + 4 records with value 0 and 1000 with value 1; D' has one more record with value 0
D = mbi.Dataset({"a": np.array([0, 1])}, mbi.Domain(["a"], [2]), weights=np.array([2**26 + 4.0, 1000.0]))
D2 = mbi.Dataset({"a": np.array([0, 1])}, mbi.Domain(["a"], [2]), weights=np.array([2**26 + 5.0, 1000.0]))
N, EPS, DELTA = 300, 1.0, 1e-5
_generate = common.generate_synthetic_data
common.generate_synthetic_data = lambda model, rng, **k: _generate(model, rng, **{**k, "rows": 1000})
mech = dpsynth.calibrate(dpsynth.discrete_mechanisms.DiscreteConfig(
    mechanism=dpsynth.discrete_mechanisms.IndependentConfig(pgm_iters=1), one_way_budget_fraction=1.0),
    None, epsilon=EPS, delta=DELTA)

rng = np.random.default_rng(0)
hits = {}
for name, data in (("D", D), ("D'", D2)):
  hits[name] = 0
  for _ in range(N):
    [m] = [m for m in mech(rng, data).measurements if m.clique == ("a",)]
    y = float(np.asarray(m.noisy_measurement)[0])
    hits[name] += y >= 2**26 + 4
  print(f"{name}: last released count {y:.1f}, stddev {float(m.stddev):.3f}")

p, p2 = hits["D"] / N, hits["D'"] / N
print(f"P_D[E] = {p:.3f}, P_D'[E] = {p2:.3f}; ({EPS}, {DELTA})-DP allows P_D'[E] <= e^eps * P_D[E] + delta = "
      f"{math.exp(EPS) * p + DELTA:.3f}")

This prints:

D: last released count 67108858.2, stddev 3.731
D': last released count 67108873.0, stddev 3.731
P_D[E] = 0.130, P_D'[E] = 0.863; (1.0, 1e-05)-DP allows P_D'[E] <= e^eps * P_D[E] + delta = 0.353
Lingua principale
Python
Stelle
32
Fork
13
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di google/dpsynth

Tutte le issue di google/dpsynth

Issue simili

Altre issue su Python

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.